oj.uz

Submission #334050

# Submission time Handle Problem Language Result Execution time Memory
334050 2020-12-08T07:52:45 Z wiwiho Tenis (COCI20_tenis) C++14
110 / 110
 239 ms 61932 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define eb emplace_back
#define printv(a, b) { \
    bool ps = false; \
    for(auto v : a){ \
        if(ps) b << " "; \
        b << v; ps = true; \
    } \
    b << "\n"; \
}
#define lsort(a) sort(iter(a))
#define int long long

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int f(int a, int b, vector<vector<int>>& rk){
    vector<pair<pii, int>> v;
    pair<pii, int> tmp = mp(mp(MAX, MAX), MAX);
    for(int i = 0; i < 3; i++){
        tmp = min(tmp, mp(mp(min(rk[a][i], rk[b][i]), max(rk[a][i], rk[b][i])), i));
    }
    //cerr << a << " " << b << "  ";
    //printv(v, cerr);
    return tmp.S;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    //cerr << "test\n";
    //n = 100000;

    vector<vector<int>> rk(n, vector<int>(3));
    vector<vector<vector<int>>> cnt(n + 1, vector<vector<int>>(8, vector<int>(3)));
    vector<ll> ans1(3);
    vector<int> ans2(n);
    vector<vector<int>> mnv(n);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < n; j++){
            int t;
            cin >> t;
            t--;
            //t = (i + j) % n;
            rk[t][i] = j;
        }
    }

    for(int i = 0; i < n; i++){
        int mn = *min_element(iter(rk[i]));
        mnv[mn].eb(i);
        for(int j = 1; j < 8; j++){
            int tmp = -1;
            for(int k = 0; k < 3; k++){
                if(!(1 << k & j)) continue;
                if(tmp == -1 || rk[i][k] < rk[i][tmp]) tmp = k;
            }
            cnt[mn][j][tmp]++;
            //cerr << i << " " << mn << " " << bitset<3>(j) << " " << tmp << "\n";
        }
    }
    //cerr << "test\n";

    for(int i = n - 1; i >= 0; i--){
        for(int j = 0; j < 8; j++){
            for(int k = 0; k < 3; k++) cnt[i][j][k] += cnt[i + 1][j][k];
            //cerr << i << " " << bitset<3>(j) << " ";
            //printv(cnt[i][j], cerr);
        }
    }
    //cerr << "test\n";

    for(int i = 0; i < n; i++){
        int mn = *min_element(iter(rk[i]));
        int tmp = 0;
        for(int j = 0; j < 3; j++){
            if(rk[i][j] == mn) tmp |= 1 << j;
        }
        for(int j = 0; j < 3; j++){
            ans1[j] += cnt[mn + 1][tmp][j];
            ans2[i] += cnt[mn + 1][tmp][j];
        }
    }
    //cerr << "test\n";
    //printv(ans1, cerr);
    //printv(ans2, cerr);

    for(int i = 0; i < n; i++){
        //cerr << i << "  ";
        //printv(mnv[i], cerr);
        for(int j : mnv[i]){
            for(int k : mnv[i]){
                if(j >= k) continue;
                //cerr << j << " " << k << "\n";
                int tmp = f(j, k, rk);
                ans1[tmp]++;
                if(rk[j][tmp] < rk[k][tmp]) ans2[j]++;
                else ans2[k]++;
            }
        }
    }
    //cerr << "test\n";

    printv(ans1, cout);
    printv(ans2, cout);
    
    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 1 ms 492 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 492 KB Output is correct
4 Correct 5 ms 2156 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 492 KB Output is correct
4 Correct 5 ms 2156 KB Output is correct
5 Correct 78 ms 23916 KB Output is correct
6 Correct 131 ms 35820 KB Output is correct
7 Correct 176 ms 47468 KB Output is correct
8 Correct 229 ms 59244 KB Output is correct
9 Correct 239 ms 58860 KB Output is correct
10 Correct 229 ms 61932 KB Output is correct