oj.uz

Submission #1082846

# Submission time Handle Problem Language Result Execution time Memory
1082846 2024-09-01T20:02:09 Z serifefedartar Tenis (COCI20_tenis) C++17
80 / 110
 72 ms 17092 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;

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};
}

int 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:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int i = 0; i < Q.size(); i++) {
      |                         ~~^~~~~~~~~~
tenis.cpp:112:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 28 ms 6620 KB Output is correct
6 Correct 44 ms 8656 KB Output is correct
7 Correct 60 ms 10696 KB Output is correct
8 Correct 72 ms 13016 KB Output is correct
9 Partially correct 68 ms 12496 KB Partially correct
10 Partially correct 69 ms 17092 KB Partially correct