Submission #366537

#TimeUsernameProblemLanguageResultExecution timeMemory
366537ne4eHbKaTenis (COCI20_tenis)C++17
110 / 110
134 ms14316 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; const int N = 1e5 + 5; struct fenwick { int f[N] {}; void add(int i) {for(i = N - 2 - i; i < N; i += i & -i) ++f[i];} int get(int i) {int v{}; for(i = N - 2 - i; i; i -= i & -i) v += f[i]; return v;} }; fenwick f0, f01, f02, f012, f1, f10, f12, f102, f2, f20, f21, f201; int p0[N], p1[N], p2[N], r0[N], r1[N], r2[N], n, p[N], s[N]; ll c0, c1, c2; void add(ll &a, int &b, const int c) { a += c; b += c; } int min(const int a, const int b, const int c) { return min(a, min(b, c)); } set<pii> f; void check(int i, int j) { if(p[i] != p[j]) return; f.insert({i, j}); } void solve() { cin >> n; for(int i = 0; i < n; ++i) cin >> r0[i], p0[--r0[i]] = i; for(int i = 0; i < n; ++i) cin >> r1[i], p1[--r1[i]] = i; for(int i = 0; i < n; ++i) cin >> r2[i], p2[--r2[i]] = i; for(int i = 0; i < n; ++i) p[i] = min(p0[i], p1[i], p2[i]); for(int i = n - 1; ~i; --i) { int v; bool b0, b1; v = r0[i]; if(p1[v] > i && p2[v] > i) add(c0, s[v], f0 .get(i + 1)), check(v, r1[i]), check(v, r2[i]); if(p1[v] == i && p2[v] > i) add(c0, s[v], f01 .get(i + 1)), check(v, r2[i]); if(p1[v] > i && p2[v] == i) add(c0, s[v], f02 .get(i + 1)), check(v, r1[i]) ; if(p1[v] == i && p2[v] == i) add(c0, s[v], f012.get(i + 1)) ; v = r1[i]; if(p0[v] > i && p2[v] > i) add(c1, s[v], f1 .get(i + 1)), check(v, r0[i]), check(v, r2[i]); if(p0[v] == i && p2[v] > i) add(c1, s[v], f10 .get(i + 1)), check(v, r2[i]); if(p0[v] > i && p2[v] == i) add(c1, s[v], f12 .get(i + 1)), check(v, r0[i]) ; if(p0[v] == i && p2[v] == i) add(c1, s[v], f102.get(i + 1)) ; v = r2[i]; if(p0[v] > i && p1[v] > i) add(c2, s[v], f2 .get(i + 1)), check(v, r0[i]), check(v, r1[i]); if(p0[v] == i && p1[v] > i) add(c2, s[v], f20 .get(i + 1)), check(v, r1[i]); if(p0[v] > i && p1[v] == i) add(c2, s[v], f21 .get(i + 1)), check(v, r0[i]) ; if(p0[v] == i && p1[v] == i) add(c2, s[v], f201.get(i + 1)) ; v = r0[i]; b0 = p1[v] >= i; b1 = p2[v] >= i; f0.add(p[v]); if(b0) f01.add(p[v]); if(b1) f02.add(p[v]); if(b0 && b1) f012.add(p[v]); v = r1[i]; b0 = p0[v] > i; b1 = p2[v] >= i; f1.add(p[v]); if(b0) f10.add(p[v]); if(b1) f12.add(p[v]); if(b0 && b1) f102.add(p[v]); v = r2[i]; b0 = p0[v] > i; b1 = p1[v] > i; f2.add(p[v]); if(b0) f20.add(p[v]); if(b1) f21.add(p[v]); if(b0 && b1) f201.add(p[v]); } for(const pii &P : f) { int i, j; tie(i, j) = P; typedef tuple<int, int, int> ti; ti z {n, n, 0}; p0[i] < p0[j] ? umin(z, ti{p0[i], p0[j], 1}) : umin(z, ti{p0[j], p0[i], 0}); p1[i] < p1[j] ? umin(z, ti{p1[i], p1[j], 3}) : umin(z, ti{p1[j], p1[i], 2}); p2[i] < p2[j] ? umin(z, ti{p2[i], p2[j], 5}) : umin(z, ti{p2[j], p2[i], 4}); int fi, se, th; tie(fi, se, th) = z; if((th & 1) && fi < n) add(th > 1 ? th > 3 ? c2 : c1 : c0, s[i], 1); } cout << c0 _ c1 _ c2 << '\n'; for(int i = 0; i < n; ++i) cout << s[i] << ' '; cout << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...