oj.uz

Submission #414613

# Submission time Handle Problem Language Result Execution time Memory
414613 2021-05-30T18:09:29 Z Odavey Carnival Tickets (IOI20_tickets) C++14
100 / 100
 1509 ms 167052 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

void allocate_tickets(vector<vector<int> > s);

//void allocate_tickets(vector<vector<int> > s){
//    for(vector<int>& v : s){
//        for(int x : v){
//            cout << x << ' ';
//        }
//        cout << endl;
//    }
//    cout << endl;
//    return;
//}

ll find_maximum(int k, vector<vector<int> > x){
    int n = x.size();
    int m = x[0].size();
    vector<vector<int> > ans;
    for(int i=0;i<n;++i){
        vector<int> tmp;
        for(int j=0;j<m;++j){
            tmp.pb(-1);
        }
        ans.pb(tmp);
    }

    pair<ll, int> rows[n][m];
    priority_queue<pair<ll, int> > minus[n], none[n];
    priority_queue<pair<ll, int> > over;//Gain, i pos
    char state[n][m];
    ll res = 0ll;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            rows[i][j].fi = x[i][j];
            rows[i][j].se = j;
        }
        sort(rows[i], rows[i]+m);
        reverse(rows[i], rows[i]+m);
        for(int j=m-k;j<m;++j){
            minus[i].push({rows[i][j].fi, rows[i][j].se});//val, j pos
            res -= rows[i][j].fi;
            state[i][rows[i][j].se] = '-';
        }
        for(int j=0;j<m-k;++j){
            none[i].push({rows[i][j].fi, rows[i][j].se});//val, j pos
            state[i][rows[i][j].se] = 'o';
        }
        if(!none[i].empty()){
            over.push({none[i].top().fi + minus[i].top().fi, i});
        }else{
            over.push({2ll*minus[i].top().fi, i});
        }
    }

    int cnt = k*n/2;
    while(cnt--){
        auto p = over.top();
        over.pop();
        int i = p.se;
        int j_minus = minus[i].top().se;
        minus[i].pop();
        res += p.fi;
        if(!none[i].empty()){
            int j_none = none[i].top().se;
            none[i].pop();

            none[i].push({x[i][j_minus], j_minus});
            if(!minus[i].empty()){
                over.push({none[i].top().fi + minus[i].top().fi, i});
            }

            state[i][j_none] = '+';
            state[i][j_minus] = 'o';
        }else{
            if(!minus[i].empty()){
                over.push({2ll*minus[i].top().fi, i});
            }

            state[i][j_minus] = '+';
        }
    }

    vector<int> P[n], M[n];
    pair<int, int> reg[n];
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(state[i][j] == '+'){
                P[i].pb(j);
            }
            if(state[i][j] == '-'){
                M[i].pb(j);
            }
        }
        reg[i] = {P[i].size(), i};
    }

//    for(int i=0;i<n;++i){
//        for(int j=0;j<m;++j){
//            cout << state[i][j];
//        }
//        cout << endl;
//    }
//    cout << endl;

    for(int i=0;i<k;++i){
        sort(reg, reg+n);
        reverse(reg, reg+n);
        for(int j=0;j<n/2;++j){
            int id = reg[j].se;
            ans[id][P[id].back()] = i;
            P[id].pop_back();
            --reg[j].fi;
        }
        for(int j=n/2;j<n;++j){
            int id = reg[j].se;
            ans[id][M[id].back()] = i;
            M[id].pop_back();
        }
    }
    allocate_tickets(ans);
    return res;
}

//int main(){
//    int k;
//    int n, m;
//    cin >> k >> n >> m;
//    vector<vector<int> > v;
//    for(int i=0;i<n;++i){
//        vector<int> tmp;
//        for(int j=0;j<m;++j){
//            int x;
//            cin >> x;
//            tmp.pb(x);
//        }
//        v.pb(tmp);
//    }
//    cout << find_maximum(k, v) << endl;
//}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 944 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 34 ms 7124 KB Output is correct
6 Correct 715 ms 131708 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 34 ms 6768 KB Output is correct
6 Correct 836 ms 147716 KB Output is correct
7 Correct 925 ms 138600 KB Output is correct
8 Correct 5 ms 972 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 10 ms 1752 KB Output is correct
13 Correct 30 ms 5192 KB Output is correct
14 Correct 30 ms 5296 KB Output is correct
15 Correct 986 ms 155092 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 884 KB Output is correct
5 Correct 45 ms 7752 KB Output is correct
6 Correct 7 ms 1372 KB Output is correct
7 Correct 10 ms 1868 KB Output is correct
8 Correct 1350 ms 166996 KB Output is correct
9 Correct 1244 ms 157120 KB Output is correct
10 Correct 1249 ms 156048 KB Output is correct
11 Correct 1361 ms 167052 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 744 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 4 ms 688 KB Output is correct
12 Correct 4 ms 844 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 744 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 716 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 4 ms 688 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 31 ms 7108 KB Output is correct
14 Correct 33 ms 7364 KB Output is correct
15 Correct 39 ms 7492 KB Output is correct
16 Correct 51 ms 7848 KB Output is correct
17 Correct 2 ms 448 KB Output is correct
18 Correct 4 ms 716 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 38 ms 6212 KB Output is correct
21 Correct 40 ms 6700 KB Output is correct
22 Correct 42 ms 7056 KB Output is correct
23 Correct 43 ms 7620 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 944 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 34 ms 7124 KB Output is correct
12 Correct 715 ms 131708 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 34 ms 6768 KB Output is correct
18 Correct 836 ms 147716 KB Output is correct
19 Correct 925 ms 138600 KB Output is correct
20 Correct 5 ms 972 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 10 ms 1752 KB Output is correct
25 Correct 30 ms 5192 KB Output is correct
26 Correct 30 ms 5296 KB Output is correct
27 Correct 986 ms 155092 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 4 ms 884 KB Output is correct
32 Correct 45 ms 7752 KB Output is correct
33 Correct 7 ms 1372 KB Output is correct
34 Correct 10 ms 1868 KB Output is correct
35 Correct 1350 ms 166996 KB Output is correct
36 Correct 1244 ms 157120 KB Output is correct
37 Correct 1249 ms 156048 KB Output is correct
38 Correct 1361 ms 167052 KB Output is correct
39 Correct 1 ms 204 KB Output is correct
40 Correct 3 ms 716 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 3 ms 716 KB Output is correct
43 Correct 4 ms 716 KB Output is correct
44 Correct 4 ms 744 KB Output is correct
45 Correct 1 ms 332 KB Output is correct
46 Correct 1 ms 332 KB Output is correct
47 Correct 4 ms 716 KB Output is correct
48 Correct 4 ms 716 KB Output is correct
49 Correct 4 ms 688 KB Output is correct
50 Correct 4 ms 844 KB Output is correct
51 Correct 31 ms 7108 KB Output is correct
52 Correct 33 ms 7364 KB Output is correct
53 Correct 39 ms 7492 KB Output is correct
54 Correct 51 ms 7848 KB Output is correct
55 Correct 2 ms 448 KB Output is correct
56 Correct 4 ms 716 KB Output is correct
57 Correct 2 ms 460 KB Output is correct
58 Correct 38 ms 6212 KB Output is correct
59 Correct 40 ms 6700 KB Output is correct
60 Correct 42 ms 7056 KB Output is correct
61 Correct 43 ms 7620 KB Output is correct
62 Correct 82 ms 16640 KB Output is correct
63 Correct 92 ms 16760 KB Output is correct
64 Correct 126 ms 18164 KB Output is correct
65 Correct 493 ms 68476 KB Output is correct
66 Correct 567 ms 71300 KB Output is correct
67 Correct 9 ms 1868 KB Output is correct
68 Correct 7 ms 1304 KB Output is correct
69 Correct 780 ms 130524 KB Output is correct
70 Correct 1244 ms 163944 KB Output is correct
71 Correct 1435 ms 162916 KB Output is correct
72 Correct 1327 ms 149352 KB Output is correct
73 Correct 1509 ms 162180 KB Output is correct
74 Correct 1075 ms 146024 KB Output is correct
75 Correct 1155 ms 151384 KB Output is correct