oj.uz

Submission #330068

# Submission time Handle Problem Language Result Execution time Memory
330068 2020-11-23T16:13:44 Z phathnv Tenis (COCI20_tenis) C++11
110 / 110
 72 ms 6636 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Tenis"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;

int n, rnk[3][N], pos[3][N];

int d[8][3], mask[N];
ll cntMatch[3], cntWin[N];
int state[N];

void readInput(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int t = 0; t < 3; t++)
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            rnk[t][i] = x;
            pos[t][x] = i;
        }
}

void considerMatch(int a, int b){
    int court = -1;
    ii best = mp(N, N);
    for(int i = 0; i < 3; i++){
        ii tmp = mp(min(pos[i][a], pos[i][b]), max(pos[i][a], pos[i][b]));
        if (best > tmp){
            court = i;
            best = tmp;
        }
    }
    assert(court > -1);
    cntMatch[court]++;
    if (pos[court][a] < pos[court][b])
        cntWin[a]++;
    else
        cntWin[b]++;
}

void upd(int ind, int typ){
    for(int mask = 1; mask < 8; mask++){
        ii best = mp(N, N);
        for(int t = 0; t < 3; t++)
            if (mask & (1 << t))
                best = min(best, mp(pos[t][ind], t));
        d[mask][best.Y] += typ;
    }
}

void solve(){
    for(int i = 1; i <= n; i++)
        upd(i, 1);
    int rmn = n;
    for(int i = 1; i <= n; i++){
        for(int t = 0; t < 3; t++){
            int x = rnk[t][i];
            mask[x] |= (1 << t);

            if (state[x] > 0)
                continue;
            state[x] = 1;
            rmn--;
            upd(x, -1);
        }
        for(int t = 0; t < 3; t++){
            int x = rnk[t][i];
            if (state[x] > 1)
                continue;
            state[x] = 2;
            cntWin[x] += rmn;
            for(int j = 0; j < 3; j++)
                cntMatch[j] += d[mask[x]][j];
        }

        vector <int> imp;
        for(int t = 0; t < 3; t++)
            if (state[rnk[t][i]] == 2)
                imp.push_back(rnk[t][i]);
        sort(imp.begin(), imp.end());
        imp.resize(unique(imp.begin(), imp.end()) - imp.begin());
        for(int i = 0; i < (int) imp.size(); i++)
            for(int j = i + 1; j < (int) imp.size(); j++)
                considerMatch(imp[i], imp[j]);

        for(int t = 0; t < 3; t++)
            state[rnk[t][i]] = 3;
    }

    for(int t = 0; t < 3; t++)
        cout << cntMatch[t] << ' ';
    cout << '\n';
    for(int i = 1; i <= n; i++)
        cout << cntWin[i] << ' ';
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    solve();
    return 0;
}

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  109 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tenis.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 1 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 1 ms 364 KB Output is correct
4 Correct 2 ms 620 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 1 ms 364 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 26 ms 2796 KB Output is correct
6 Correct 39 ms 4076 KB Output is correct
7 Correct 52 ms 5356 KB Output is correct
8 Correct 69 ms 6636 KB Output is correct
9 Correct 63 ms 6636 KB Output is correct
10 Correct 72 ms 6636 KB Output is correct