Submission #930891

#	Time	Username	Problem	Language	Result	Execution time	Memory
930891		velislavgarkov	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	642 ms	109796 KiB

tickets

#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][d[i][j].ind]=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++) {
            res[i][j]=-1;
            if (pl[i][j]) pos[i].push_back(j);
            else if (mi[i][j]) 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 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10