oj.uz

Submission #358425

# Submission time Handle Problem Language Result Execution time Memory
358425 2021-01-25T13:09:09 Z egekabas Tenis (COCI20_tenis) C++14
80 / 110
 218 ms 13804 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<vector<int>> a;
int n;
int play[100009];
int court[100009];
void manual(int x, int y){
    vector<vector<int>> rnk;
    for(int i = 0; i < 3; ++i){
        rnk.pb({min(a[x][i], a[y][i]), max(a[x][i], a[y][i]), i});
    }
    sort(all(rnk));
    int cur = rnk[0][2];
    court[cur]++;
    if(a[x][cur] < a[y][cur])
        ++play[x];
    else
        ++play[y];
}
vector<int> best[100009];
int dp[(1<<3)][3];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    a = vector<vector<int>> (n, vector<int>(3));
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < n; ++j){
            int idx;
            cin >> idx;
            a[idx-1][i] = j;
        }
    for(int i = 0; i < n; ++i){
        int mini = 1e9;
        for(auto u : a[i])
            mini = min(mini, u);
        best[mini].pb(i);
    }
    for(int i = n-1; i >= 0; --i){
        for(auto idx : best[i]){
            int st = 0;
            for(int j = 0; j < 3; ++j)
                if(a[idx][j] == i)
                    st += (1<<j);
            for(int j = 0; j < 3; ++j){
                play[idx] += dp[st][j];
                court[j] += dp[st][j];
            }
        }
        for(int j = 0; j < best[i].size(); ++j)
            for(int k = j+1; k < best[i].size(); ++k)
                manual(best[i][j], best[i][k]);
        for(auto idx : best[i]){
            for(int st = 1; st < (1<<3); ++st){
                vector<pii> rnk;
                for(int j = 0; j < 3; ++j)
                    if(st&(1<<j))
                        rnk.pb({a[idx][j], j});
                sort(all(rnk));
                dp[st][rnk[0].ss]++;
            }
        }
    }
    cout << court[0] << ' ' << court[1] << ' ' << court[2] << '\n';
    for(int i = 0; i < n; ++i)
        cout << play[i] << ' ';
}

Compilation message

tenis.cpp: In function 'int main()':
tenis.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j < best[i].size(); ++j)
      |                        ~~^~~~~~~~~~~~~~~~
tenis.cpp:67:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int k = j+1; k < best[i].size(); ++k)
      |                              ~~^~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 5 ms 3052 KB Output is correct
5 Correct 63 ms 6636 KB Output is correct
6 Correct 88 ms 8684 KB Output is correct
7 Correct 153 ms 10732 KB Output is correct
8 Correct 218 ms 12652 KB Output is correct
9 Partially correct 168 ms 12396 KB Partially correct
10 Partially correct 175 ms 13804 KB Partially correct