2024 ICPC Asia Taiwan Online Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105383
比賽影片
---
No
記分板
---
是GBC不是MyGO!!!
題解
---
### A. Animal Farm
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### B. Business Magic
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### C. Cards
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }
struct FenwickTree{
vector<ll> BIT;
FenwickTree(int n) : BIT(n + 1, 0) {}
void mod(int x, ll val) {
while(x < BIT.size()){
BIT[x] += val;
x += x & -x;
}
}
ll query(int x) {
ll res = 0;
while (x) {
res += BIT[x];
x -= x & -x;
}
return res;
}
ll rquery(int l, int r) {
return query(r) - query(l - 1);
}
};
void solve() {
int n; cin >> n;
vector<pii> p(n);
for (auto &[a, b] : p) cin >> a;
for (auto &[a, b] : p) cin >> b;
sort(all(p));
FenwickTree bit(n);
ll cnt = 0;
for (auto [a, b] : p) {
cnt += b - 1 - bit.query(b);
bit.mod(b, 1);
}
if (cnt & 1) {
cout << "No\n";
return;
}
cnt /= 2;
FenwickTree bit2(n);
vector<int> pos(n + 1), ans;
rep (i, 0, n) pos[p[i].S] = p[i].F;
rep (i, 1, n + 1) {
ll sub = pos[i] + bit2.query(pos[i]) - i;
if (cnt > sub) {
bit2.mod(1, 1);
bit2.mod(pos[i], -1);
cnt -= sub;
ans.pb(pos[i] - 1);
} else {
int idx;
rep (j, 0, n) {
if (p[j].S >= i) {
if (p[j].S == i) idx = ans.size();
ans.pb(j);
}
}
while (cnt) {
cnt--;
swap(ans[idx], ans[idx - 1]);
idx--;
}
break;
}
}
assert(cnt == 0);
cout << "Yes\n";
for (int x : ans) cout << p[x].F << ' ';
cout << '\n';
for (int x : ans) cout << p[x].S << ' ';
cout << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
### D. Disbursement on Quarantine Policy
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### E. Efficient Slabstones Rearrangement
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### F. Fibonacci Lucky Numbers
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5, MOD = 10'000'000'000;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow(ll x, ll exp, ll mod = LLONG_MAX) {
ll res = 1;
while (exp) {
if(exp & 1) res = __int128(res) * x % mod;
x = __int128(x) * x % mod;
exp >>= 1;
}
return res;
}
struct Mat{
vector<vector<ll>> a;
int x, y;
Mat(int _x, int _y){
a.resize(_x, vector<ll>(_y, 0));
x = _x;
y = _y;
}
Mat operator * (Mat &inp){
Mat res(x, inp.y);
rep(i, 0, x) rep(j, 0, inp.y) rep(k, 0, y){
res.a[i][j] += __int128(a[i][k]) * inp.a[k][j] % MOD;
res.a[i][j] %= MOD;
}
return res;
}
};
void powpow(Mat &res, ll exp){
Mat base = res;
while(exp){
if(exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
}
const ll per = 150'000'000'000LL;
const ll phi = 40'000'000'000LL;
const ll phi2 = 16'000'000'000LL;
void solve() {
int n; cin >> n;
// 7^7^7^n (mod per) -> 7^(7^7^n (mod phi)) (mod per) -> 7^(7^(7^n (mod phi2)) (mod phi)) (mod per)
ll p3 = fpow(7, n, phi2);
ll p2 = fpow(7, p3, phi);
ll p1 = (fpow(7, p2, per) - 1 + per) % per;
Mat fib(2, 2); // [1, 1], [1, 0]
fib.a[0][0] = fib.a[0][1] = fib.a[1][0] = 1;
fib.a[1][1] = 0;
powpow(fib, p1);
string ans = to_string(fib.a[0][1]);
while (ans.size() < 10) ans = '0' + ans;
cout << ans << '\n';
}
int main() {
ZTMYACANESOCUTE;
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
```
:::
### G. Game of Rounding
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### H. Harmonious Passage of Magicians
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### I. In Search of the Lost Array
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### J. Just Round Down
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### K. Kingdom's Development Plan
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### L. Lexicopolis
---
#### 題目大綱
#### 想法
:::spoiler 實作
```cpp=
#ifdef LOCAL
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rep(X, a, b) for(int X = a; X < b; ++X)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#ifdef LOCAL
#define ZTMYACANESOCUTE // freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 6;
#endif
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.fi + p2.fi, p1.se + p2.se); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.fi - p2.fi, p1.se - p2.se); }
template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }
#define lpos pos << 1
#define rpos pos << 1 | 1
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
const int MAXN = 2e5 + 5, MOD2 = 998244353, IINF = 1e9 + 7, MOD = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
ll fpow (ll x, ll exp, ll mod = LLONG_MAX) { if (x == 0) return 0; ll res = 1; while (exp > 0) { if (exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1; } return res; }
#define int long long
void solve() {
int n, m, ss, tt, x, step; cin >> n >> m >> ss >> tt >> x >> step;
ss--, tt--;
// dp[i][j][t]: from i->j, length 2^t. pair: {rank (relative to same t), hash}
// dp[i][j][t] <- dp[i][k][t - 1] + dp[k][j][t - 1], min lexi.(compare {r1, r2}), hash = h1 * x^{2^{t-1}} + h2
// maybe 離散化 the rank after each round doubling
vector<int> X(30);
rep (i, 0, 30) X[i] = fpow(x, (1 << i), MOD);
vector dp(30, vector (n, vector<pii>(n, pii(-1, -1))));
rep (i, 0, m) {
int a, b, w; cin >> a >> b >> w;
a--, b--;
dp[0][a][b] = pii(w, w);
}
auto lisan = [&](vector<vector<pii>> &arr) -> void {
vector<int> dic;
rep (i, 0, n) rep (j, 0, n) if (arr[i][j].fi != -1) {
dic.pb(arr[i][j].fi);
}
sort(all(dic));
dic.erase(unique(all(dic)), dic.end());
rep (i, 0, n) rep (j, 0, n) if (arr[i][j].fi != -1) {
arr[i][j].fi = lower_bound(all(dic), arr[i][j].fi) - dic.begin();
}
};
// build doubling
lisan(dp[0]);
rep (t, 1, 30) {
rep (k, 0, n) rep (i, 0, n) rep (j, 0, n) {
auto &[r1, h1] = dp[t - 1][i][k];
auto &[r2, h2] = dp[t - 1][k][j];
auto &[r, h] = dp[t][i][j];
if (r1 == -1 || r2 == -1) continue;
if (r == -1 || r > r1 * (n * n) + r2) {
r = r1 * (n * n) + r2;
h = (h1 * X[t - 1] + h2) % MOD;
}
}
lisan(dp[t]);
}
// jump
vector cur(n, vector<pii>(n, pii(-1, -1)));
cur[ss][ss] = {0, 0};
rep (t, 0, 30) if (step >> t & 1) {
vector nxt(n, vector<pii>(n, pii(-1, -1)));
rep (k, 0, n) rep (i, 0, n) rep (j, 0, n) {
auto &[r1, h1] = cur[i][k];
auto &[r2, h2] = dp[t][k][j];
auto &[r, h] = nxt[i][j];
if (r1 == -1 || r2 == -1) continue;
if (r == -1 || r > r1 * (n * n) + r2) {
r = r1 * (n * n) + r2;
h = (h1 * X[t] + h2) % MOD;
}
}
swap(cur, nxt);
lisan(cur);
}
cout << cur[ss][tt].se << '\n';
}
signed main() {
ZTMYACANESOCUTE;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
```
:::
Sign in with Wallet
Connect another wallet