Submission #334050

#TimeUsernameProblemLanguageResultExecution timeMemory
334050wiwihoTenis (COCI20_tenis)C++14
110 / 110
239 ms61932 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define iter(a) a.begin(), a.end() #define eb emplace_back #define printv(a, b) { \ bool ps = false; \ for(auto v : a){ \ if(ps) b << " "; \ b << v; ps = true; \ } \ b << "\n"; \ } #define lsort(a) sort(iter(a)) #define int long long using namespace std; typedef long long ll; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } int f(int a, int b, vector<vector<int>>& rk){ vector<pair<pii, int>> v; pair<pii, int> tmp = mp(mp(MAX, MAX), MAX); for(int i = 0; i < 3; i++){ tmp = min(tmp, mp(mp(min(rk[a][i], rk[b][i]), max(rk[a][i], rk[b][i])), i)); } //cerr << a << " " << b << " "; //printv(v, cerr); return tmp.S; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; //cerr << "test\n"; //n = 100000; vector<vector<int>> rk(n, vector<int>(3)); vector<vector<vector<int>>> cnt(n + 1, vector<vector<int>>(8, vector<int>(3))); vector<ll> ans1(3); vector<int> ans2(n); vector<vector<int>> mnv(n); for(int i = 0; i < 3; i++){ for(int j = 0; j < n; j++){ int t; cin >> t; t--; //t = (i + j) % n; rk[t][i] = j; } } for(int i = 0; i < n; i++){ int mn = *min_element(iter(rk[i])); mnv[mn].eb(i); for(int j = 1; j < 8; j++){ int tmp = -1; for(int k = 0; k < 3; k++){ if(!(1 << k & j)) continue; if(tmp == -1 || rk[i][k] < rk[i][tmp]) tmp = k; } cnt[mn][j][tmp]++; //cerr << i << " " << mn << " " << bitset<3>(j) << " " << tmp << "\n"; } } //cerr << "test\n"; for(int i = n - 1; i >= 0; i--){ for(int j = 0; j < 8; j++){ for(int k = 0; k < 3; k++) cnt[i][j][k] += cnt[i + 1][j][k]; //cerr << i << " " << bitset<3>(j) << " "; //printv(cnt[i][j], cerr); } } //cerr << "test\n"; for(int i = 0; i < n; i++){ int mn = *min_element(iter(rk[i])); int tmp = 0; for(int j = 0; j < 3; j++){ if(rk[i][j] == mn) tmp |= 1 << j; } for(int j = 0; j < 3; j++){ ans1[j] += cnt[mn + 1][tmp][j]; ans2[i] += cnt[mn + 1][tmp][j]; } } //cerr << "test\n"; //printv(ans1, cerr); //printv(ans2, cerr); for(int i = 0; i < n; i++){ //cerr << i << " "; //printv(mnv[i], cerr); for(int j : mnv[i]){ for(int k : mnv[i]){ if(j >= k) continue; //cerr << j << " " << k << "\n"; int tmp = f(j, k, rk); ans1[tmp]++; if(rk[j][tmp] < rk[k][tmp]) ans2[j]++; else ans2[k]++; } } } //cerr << "test\n"; printv(ans1, cout); printv(ans2, cout); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...