oj.uz

Submission #498591

# Submission time Handle Problem Language Result Execution time Memory
498591 2021-12-25T15:18:53 Z Victor Tenis (COCI20_tenis) C++17
110 / 110
 259 ms 19680 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

ll best[100001], n, court_ans[100001], wins[100001], cnt[27], people_ranks[100001][3];
vll order[100001], people_ranks_compressed[100001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(court_ans, 0, sizeof(court_ans));
    fill(best,best+100001,INF);
    memset(wins, 0, sizeof(wins));
    memset(cnt, 0, sizeof(cnt));

    cin >> n;
    rep(j, 0, 3) {
        rep(i, 0, n) {
            ll person;
            cin >> person;
            --person;
            best[person] = min(best[person], ll(i));
            people_ranks_compressed[person].pb(i);
            people_ranks[person][j] = i;
        }
    }


    rep(i, 0, n) {
        order[best[i]].pb(i);
        vll &cur = people_ranks_compressed[i];
        set<ll> s;
        umap<ll, ll> compress;

        trav(rank, cur) s.insert(rank);

        ll pos = 0;
        trav(rank, s) compress[rank] = pos++;

        ll sum = 0, mult = 9;
        trav(rank, cur) {
            rank = compress[rank];
            sum += rank * mult;
            mult /= 3;
        }
        ++cnt[sum];
    }

    ll bad = n;
    rep(rank, 0, n) {
        vll cur_people = order[rank];
        if (cur_people.empty()) continue;

        bad -= sz(cur_people);
        trav(person, cur_people) {
            wins[person] += bad;
            //cout<<"person = "<<person<<" bad = "<<bad<<endl;
            ll sum = 0, mult = 9;
            trav(rank, people_ranks_compressed[person]) {
                sum += rank * mult;
                mult /= 3;
            }
            --cnt[sum];
        }

        trav(person, cur_people) {
            vll my_ranks = people_ranks_compressed[person];
            vll cur_ranks(3);
            rep(i, 0, 3) {
                cur_ranks[0] = i;
                rep(j, 0, 3) {
                    cur_ranks[1] = j;
                    rep(k, 0, 3) {
                        cur_ranks[2] = k;
                        ll sum = 9 * i + 3 * j + k;
                        ll court = -1, rank2 = INF;

                        rep(l, 0, 3) if (!my_ranks[l] && cur_ranks[l] < rank2) {
                            rank2 = cur_ranks[l];
                            court = l;
                        }

                        court_ans[court] += cnt[sum];
                    }
                }
            }
        }

        rep(i, 0, ll(sz(cur_people) - 1)) rep(j, i + 1, ll(sz(cur_people))) {
            ll p1 = cur_people[i], p2 = cur_people[j];
            ll court, rank2 = INF;
            ll winner = p1;
            rep(k, 0, 3) {
                if (!people_ranks_compressed[p1][k] && people_ranks[p2][k] < rank2) {
                    court = k;
                    rank2 = people_ranks[p2][k];
                    winner = p1;
                }
                if (!people_ranks_compressed[p2][k] && people_ranks[p1][k] < rank2) {
                    court = k;
                    rank2 = people_ranks[p1][k];
                    winner = p2;
                }
            }
            ++wins[winner];
            ++court_ans[court];
        }
    }

    rep(i, 0, 3) cout << court_ans[i] << ' ';
    cout << endl;
    rep(i, 0, n) cout << wins[i] << ' ';
    cout << endl;
    return 0;
}

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:135:13: warning: 'court' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |             ++court_ans[court];
      |             ^~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7288 KB Output is correct
4 Correct 9 ms 7640 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7288 KB Output is correct
4 Correct 9 ms 7640 KB Output is correct
5 Correct 109 ms 11948 KB Output is correct
6 Correct 119 ms 14332 KB Output is correct
7 Correct 166 ms 16708 KB Output is correct
8 Correct 259 ms 19088 KB Output is correct
9 Correct 195 ms 18320 KB Output is correct
10 Correct 199 ms 19680 KB Output is correct