oj.uz

Submission #1083204

# Submission time Handle Problem Language Result Execution time Memory
1083204 2024-09-02T18:04:53 Z serifefedartar Tenis (COCI20_tenis) C++17
110 / 110
 80 ms 20424 KB 
#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

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++) {
      |                               ~~^~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 2 ms 1628 KB Output is correct
5 Correct 29 ms 7380 KB Output is correct
6 Correct 38 ms 10444 KB Output is correct
7 Correct 59 ms 13516 KB Output is correct
8 Correct 71 ms 16660 KB Output is correct
9 Correct 64 ms 15944 KB Output is correct
10 Correct 80 ms 20424 KB Output is correct