Submission #330068

#	Time	Username	Problem	Language	Result	Execution time	Memory
330068		phathnv	Tenis (COCI20_tenis)	C++11	110 / 110	72 ms	6636 KiB

tenis

#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 (stderr)

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 / 35
• Subtask 2: 15 / 15
• Subtask 3: 60 / 60