Submission #1083204

#TimeUsernameProblemLanguageResultExecution timeMemory
1083204serifefedartarTenis (COCI20_tenis)C++17
110 / 110
80 ms20424 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0) typedef long long ll; #define f first #define s second #define LOGN 21 const ll MOD = 1e9 + 7; const ll MAXN = 1e5 + 100; #define int long long int v[4][MAXN], inv[4][MAXN]; int mn[MAXN], cnt[4], ans[MAXN]; pair<int,int> get_winner(int A, int B) { vector<pair<pair<int,int>,int>> possible; possible.push_back({{inv[1][A], inv[1][B]}, 1}); possible.push_back({{inv[2][A], inv[2][B]}, 2}); possible.push_back({{inv[3][A], inv[3][B]}, 3}); sort(possible.begin(), possible.end(), [&](pair<pair<int,int>,int> A, pair<pair<int,int>,int> B) { return make_pair(make_pair(min(A.f.f, A.f.s), max(A.f.f, A.f.s)), A.s) < make_pair(make_pair(min(B.f.f, B.f.s), max(B.f.f, B.f.s)), B.s); }); if (possible[0].f.f < possible[0].f.s) return {A, possible[0].s}; else return {B, possible[0].s}; } signed main() { fast; int N; cin >> N; for (int i = 0; i < MAXN; i++) mn[i] = 1e9; for (int i = 1; i <= 3; i++) { for (int j = 1; j <= N; j++) { cin >> v[i][j]; inv[i][v[i][j]] = j; mn[v[i][j]] = min(mn[v[i][j]], j); } } vector<pair<int,int>> v2; for (int i = 1; i <= N; i++) v2.push_back({mn[i], i}); sort(v2.begin(), v2.end(), greater<pair<int,int>>()); int cc = 0; map<int,vector<int>> mp; map<pair<int,int>,int> counter; for (int i = 0; i < N; i++) { if (i != 0 && v2[i-1].f != v2[i].f) { for (int j = i-1; j >= 0; j--) { if (v2[j].f != v2[i-1].f) break; int x = v2[j].s; if (inv[1][x] <= inv[2][x] && inv[1][x] <= inv[3][x]) counter[{1, -1}]++; if (inv[2][x] < inv[1][x] && inv[2][x] <= inv[3][x]) counter[{2, -1}]++; if (inv[3][x] < inv[2][x] && inv[3][x] < inv[1][x]) counter[{3, -1}]++; if (inv[1][x] <= inv[2][x]) counter[{1, 2}]++; if (inv[1][x] <= inv[3][x]) counter[{1, 3}]++; if (inv[2][x] < inv[1][x]) counter[{2, 1}]++; if (inv[2][x] <= inv[3][x]) counter[{2, 3}]++; if (inv[3][x] < inv[1][x]) counter[{3, 1}]++; if (inv[3][x] < inv[2][x]) counter[{3, 2}]++; } } pair<int,int> u = v2[i]; mp[u.f].push_back(u.s); cc++; ans[u.s] = cc - mp[u.f].size(); vector<int> canditate; for (int i = 1; i <= 3; i++) { if (inv[i][u.s] == u.f) canditate.push_back(i); } if (canditate.size() == 1) cnt[canditate[0]] += cc - mp[u.f].size(); else if (canditate.size() == 2) { cnt[canditate[0]] += counter[{canditate[0], canditate[1]}]; cnt[canditate[1]] += counter[{canditate[1], canditate[0]}]; } else { cnt[canditate[0]] += counter[{canditate[0], -1}]; cnt[canditate[1]] += counter[{canditate[1], -1}]; cnt[canditate[2]] += counter[{canditate[2], -1}]; } } for (auto u : mp) { vector<int> Q = u.s; for (int i = 0; i < Q.size(); i++) { for (int j = i+1; j < Q.size(); j++) { pair<int,int> P = get_winner(Q[i], Q[j]); cnt[P.s]++; ans[P.f]++; } } } cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << "\n"; for (int i = 1; i <= N; i++) cout << ans[i] << " "; cout << "\n"; }

Compilation message (stderr)

tenis.cpp: In function 'int main()':
tenis.cpp:113:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for (int i = 0; i < Q.size(); i++) {
      |                         ~~^~~~~~~~~~
tenis.cpp:114:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int j = i+1; j < Q.size(); j++) {
      |                               ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...