oj.uz

Submission #379140

# Submission time Handle Problem Language Result Execution time Memory
379140 2021-03-17T10:23:19 Z NONAME Tenis (COCI20_tenis) C++17
110 / 110
 676 ms 13500 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int man = (int)(1e5 + 500);

int n;
long long courts[man], lose[man], mn[man];
int a[3][man], loc[3][man];
vector <int> v[8];
map <pair <int, int>, pair <int, int> > mp;
map <pair <int, int>, bool> was;

void check(int x, int t1, int t2) {
    if ((t1 == t2) || (loc[t1][x] != mn[x])) {
        return;
    }
    int y = a[t2][mn[x]];
    // cerr << (t1 + 1) << " " << (t2 + 1) << " " << (x + 1) << " " << (y + 1) << "\n";
    if ((mn[y] != mn[x]) || (x == y)) {
        return;
    }

    int xx = x, yy = y;
    if (xx > yy) {
        swap(xx, yy);
    }

    if (!was[{xx, yy}]) {
        was[{xx, yy}] = true;
        if (loc[t1][y] < loc[t2][x]) {
            mp[{xx, yy}] = {loc[t1][y], t1};
        } else if (loc[t2][x] < loc[t1][y]) {
            mp[{xx, yy}] = {loc[t2][x], t2};
        } else {
            if (t1 < t2) {
                mp[{xx, yy}] = {loc[t1][y], t1};
            } else {
                mp[{xx, yy}] = {loc[t2][x], t2};
            }
        }
    } else {
        pair <int, int> c1, c2 = mp[{xx, yy}];
        if (loc[t1][y] < loc[t2][x]) {
            c1 = {loc[t1][y], t1};
        } else if (loc[t2][x] < loc[t1][y]) {
            c1 = {loc[t2][x], t2};
        } else {
            if (t1 < t2) {
                c1 = {loc[t1][y], t1};
            } else {
                c1 = {loc[t2][x], t2};
            }
        }

        mp[{xx, yy}] = min(c1, c2);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        mn[i] = n;
    }
    for (int t = 0; t < 3; ++t) {
        for (int i = 0; i < n; ++i) {
            int& x = a[t][i];
            cin >> x;
            --x;
            loc[t][x] = i;
            mn[x] = min(mn[x], (long long)(i));
        }
    }
    cerr << "\n";

    for (int i = 0; i < n; ++i) {
        int msk = 0;
        for (int t = 0; t < 3; ++t) {
            if (mn[i] == loc[t][i]) {
                msk |= (1 << t);
            }
        }

        v[msk].push_back(mn[i]);
    }

    for (int i = 0; i < 8; ++i) {
        sort(v[i].begin(), v[i].end());
    }

    for (int i = 0; i < n; ++i) {
        for (int msk = 1; msk < 8; ++msk) {
            int ps = lower_bound(v[msk].begin(), v[msk].end(), mn[i]) - v[msk].begin();
            int wn = -1;
            for (int t = 0; t < 3; ++t) {
                if ((msk >> t) & 1) {
                    if ((wn == -1) || (loc[t][i] < loc[wn][i])) {
                        wn = t;
                    }
                }
            }
            // cerr << i << " " << ps << " " << wn << " " << msk << "\n";
            courts[wn] += ps;
            lose[i] += ps;
        }
    }

    for (int i = 0; i < 3; ++i) {
        cerr << courts[i] << " ";
    }
    cerr << "\n";
    for (int i = 0; i < n; ++i) {
        cerr << lose[i] << " ";
    }
    cerr << "\n\n";

    for (int i = 0; i < n; ++i) {
        for (int t1 = 0; t1 < 3; ++t1) {
            for (int t2 = 0; t2 < 3; ++t2) {
                check(i, t1, t2);
            }
        }
    }
    cerr << "\n";

    for (auto& i : mp) {
        // cerr << (i.first.first + 1) << " " << (i.first.second + 1) << " " << (a[i.second.second][i.second.first] + 1) << " " << (i.second.second + 1) << "\n";
        ++courts[i.second.second];
        ++lose[a[i.second.second][i.second.first]];
    }

    for (int i = 0; i < 3; ++i) {
        cout << courts[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < n; ++i) {
        cout << (n - 1 - lose[i]) << " ";
    }
    cout << "\n";

    return 0;
}

Subtask #1
35.0 / 35.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 17 ms 748 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 17 ms 748 KB Output is correct
5 Correct 285 ms 5628 KB Output is correct
6 Correct 378 ms 8220 KB Output is correct
7 Correct 523 ms 10856 KB Output is correct
8 Correct 669 ms 13500 KB Output is correct
9 Correct 676 ms 12648 KB Output is correct
10 Correct 590 ms 7068 KB Output is correct