Submission #366785

#TimeUsernameProblemLanguageResultExecution timeMemory
366785kartelTenis (COCI20_tenis)C++14
110 / 110
156 ms8164 KiB
#include <bits/stdc++.h> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) //#include <time.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") #define F first #define S second #define pb push_back #define M ll(1e9 + 7) #define sz(x) (int)x.size() #define re return #define oo ll(1e18) #define el '\n' #define pii pair <int, int> #define all(x) (x).begin(), (x).end() #define arr_all(x, n) (x + 1), (x + 1 + n) #define vi vector<int> using namespace std; typedef long long ll; //using namespace __gnu_pbds; //typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long double ld; typedef unsigned long long ull; typedef short int si; const int N = 1e5 + 500; set <pii> se; int where[N][4]; int a[4][N]; int mn[N]; vector <int> bestest[9]; ll cnt[4], ans[N], n; void check(int a, int b, int p) { if (a == b || mn[a] != p || mn[b] != p) return; pii P = {min(a, b), max(a, b)}; if (se.count(P)) return; se.insert(P); pii p0 = {min(where[a][0], where[b][0]), max(where[a][0], where[b][0])}; pii p1 = {min(where[a][1], where[b][1]), max(where[a][1], where[b][1])}; pii p2 = {min(where[a][2], where[b][2]), max(where[a][2], where[b][2])}; if (p2 < p1 && p2 < p0) { cnt[2]++; ans[a] += (where[a][2] > where[b][2]); ans[b] += (where[b][2] > where[a][2]); } else if (p1 < p0) { cnt[1]++; ans[a] += (where[a][1] > where[b][1]); ans[b] += (where[b][1] > where[a][1]); } else { cnt[0]++; ans[a] += (where[a][0] > where[b][0]); ans[b] += (where[b][0] > where[a][0]); } } int main() { // mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());; ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // in("volley.in"); // out("volley.out"); // in("input.txt"); // out("output.txt"); // clock_t tStart = clock(); cin >> n; for (int i = 0; i < 3; i++) { for (int j = 0; j < n; j++) { int x; cin >> x; x--; a[i][j] = x; where[x][i] = j; } } for (int i = 0; i < n; i++) { mn[i] = min({where[i][0], where[i][1], where[i][2]}); int mask = 0; for (int j = 0; j < 3; j++) { if (where[i][j] == mn[i]) { mask |= (1 << j); } } // cerr << i << " " << mask << el; bestest[mask].pb(mn[i]); } for (int i = 0; i < 8; i++) { sort(all(bestest[i])); } for (int i = 0; i < n; i++) { for (int mask = 1; mask < 8; mask++) { int ps = lower_bound(all(bestest[mask]), mn[i]) - bestest[mask].begin(); int p = -1; for (int k = 0; k < 3; k++) { if (!(mask & (1 << k))) continue; if (p == -1 || where[i][k] < where[i][p]) p = k; } // cout << i << " " << mask << " " << ps << " " << p << el; assert(p != -1); cnt[p] += ps; ans[i] += ps; } } for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) for (int k = j + 1; k < 3; k++) { check(a[j][i], a[k][i], i); } } for (int i = 0; i < 3; i++) { cout << cnt[i] << " "; } cout << el; for (int i = 0; i < n; i++) cout << n - 1 - ans[i] << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...