oj.uz

Submission #930884

# Submission time Handle Problem Language Result Execution time Memory
930884 2024-02-20T15:04:29 Z velislavgarkov Carnival Tickets (IOI20_tickets) C++14
76 / 100
 653 ms 110468 KB 
#include "tickets.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct Change {
    long long s;
    int col;
    int sm, b;
    bool friend operator < (Change a, Change b) {
        return a.s<b.s;
    }
};
struct Element {
    int x;
    int ind;
    bool friend operator < (Element a, Element b) {
        return a.x<b.x;
    }
};
struct Color {
    int ss;
    int ind;
    bool friend operator < (Color a, Color b) {
        return a.ss<b.ss;
    }
};
const int MAXN=1501;
priority_queue <Change> q;
bool mi[MAXN][MAXN], pl[MAXN][MAXN], positive[MAXN];
vector <vector <int> > res;
vector <vector <Element> > d;
vector <int> pos[MAXN], neg[MAXN];
Color a[MAXN];
int n, m;
long long ans;
long long find_maximum(int k, vector<vector<int> > d1) {
    n=d1.size();
    m=d1[0].size();
    res.resize(n);
    d.resize(n);
    ans=0;
    for (int i=0;i<n;i++) {
        res[i].resize(m);
        d[i].resize(m);
        for (int j=0;j<m;j++) {
            d[i][j].x=d1[i][j];
            d[i][j].ind=j;
        }
        sort(d[i].begin(),d[i].end());
        for (int j=0;j<k;j++) {
            ans-=d[i][j].x;
            mi[i][j]=true;
        }
        q.push({d[i][m-1].x+d[i][k-1].x,i,k-1,m-1});
    }
    for (int times=0;times<k*n/2;times++) {
        auto t=q.top();
        ans+=t.s;
        mi[t.col][d[t.col][t.sm].ind]=false;
        pl[t.col][d[t.col][t.b].ind]=true;
        q.pop();
        if (t.sm==0) continue;
        q.push({d[t.col][t.sm-1].x+d[t.col][t.b-1].x,t.col,t.sm-1,t.b-1});
    }
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (!mi[i][j] && !pl[i][j]) res[i][j]=-1;
            else if (pl[i][j]) pos[i].push_back(j);
            else neg[i].push_back(j);
        }
    }
    for (int i=0;i<k;i++) {
        memset(positive,false,sizeof(positive));
        for (int j=0;j<n;j++) {
            if (!pos[j].empty()) a[j].ss=-pos[j].size();
            else a[j].ss=0;
            a[j].ind=j;
        }
        sort(a,a+n);
        for (int j=0;j<n/2;j++) {
            int cur=a[j].ind;
            res[cur][pos[cur].back()]=i;
            positive[cur]=true;
            pos[cur].pop_back();
        }
        for (int j=0;j<n;j++) {
            if (positive[j]) continue;
            res[j][neg[j].back()]=i;
            neg[j].pop_back();
        }
    }
    allocate_tickets(res);
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 18 ms 7256 KB Output is correct
6 Correct 420 ms 73556 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2560 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 2 ms 4700 KB There is multiple tickets of color 0 on day 0
5 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2564 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 4876 KB Output is correct
5 Correct 23 ms 8792 KB Output is correct
6 Correct 4 ms 3160 KB Output is correct
7 Correct 6 ms 5724 KB Output is correct
8 Correct 653 ms 110352 KB Output is correct
9 Correct 617 ms 104024 KB Output is correct
10 Correct 618 ms 103272 KB Output is correct
11 Correct 613 ms 110468 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 18 ms 8188 KB Output is correct
14 Correct 18 ms 8284 KB Output is correct
15 Correct 21 ms 8540 KB Output is correct
16 Correct 22 ms 8796 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 2 ms 4700 KB Output is correct
20 Correct 18 ms 7908 KB Output is correct
21 Correct 21 ms 8540 KB Output is correct
22 Correct 20 ms 8280 KB Output is correct
23 Correct 22 ms 8540 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 18 ms 7256 KB Output is correct
12 Correct 420 ms 73556 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2560 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Incorrect 2 ms 4700 KB There is multiple tickets of color 0 on day 0
17 Halted 0 ms 0 KB -