oj.uz

Submission #333934

# Submission time Handle Problem Language Result Execution time Memory
333934 2020-12-08T03:37:20 Z wiwiho Tenis (COCI20_tenis) C++14
50 / 110
 1000 ms 26348 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))

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;
    for(int i = 0; i < 3; i++){
        v.eb(mp(mp(min(rk[a][i], rk[b][i]), max(rk[a][i], rk[b][i])), i));
    }
    lsort(v);
    //cerr << a << " " << b << "  ";
    //printv(v, cerr);
    return v[0].S;
}

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

    int n;
    cin >> n;

    vector<vector<int>> rk(n, vector<int>(3));
    vector<vector<vector<int>>> cnt(n + 1, vector<vector<int>>(8, vector<int>(3)));
    vector<int> 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;
            rk[t - 1][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";
        }
    }

    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);
        }
    }

    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];
        }
    }
    //printv(ans1, cerr);
    //printv(ans2, cerr);

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

    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 4 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 4 ms 492 KB Output is correct
4 Correct 304 ms 2332 KB Output is correct

Subtask #3
0.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 4 ms 492 KB Output is correct
4 Correct 304 ms 2332 KB Output is correct
5 Execution timed out 1086 ms 26348 KB Time limit exceeded
6 Halted 0 ms 0 KB -