Submission #640135

#	Time	Username	Problem	Language	Result	Execution time	Memory
640135		lis05st	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	713 ms	67212 KiB

tickets

#ifdef LIS05ST
    #define _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"tickets.h"
#include"bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
const int NMAX=1500;
int p1[NMAX+5],p2[NMAX+5];
int cnt2[NMAX+5];

vector<int>plusa[NMAX+5],minusa[NMAX+5];

long long find_maximum(signed k, std::vector<std::vector<signed>> d){
    int n=d.size();int m=d[0].size();
    vector<vector<signed>>ans(n,vector<signed>(m,-1));
    for(int i=0;i<n;i++)for(int ii=0;ii<m;ii++)ans[i][0]=-1;

    priority_queue<pair<int,int>>q;
    ll res=0;
    for(int i=0;i<n;i++){
        p1[i]=k-1;
        p2[i]=m-1;
        for(int ii=0;ii<k;ii++){
            res-=d[i][ii];
        }
        q.push({d[i][p2[i]]+d[i][p1[i]],i});
    }
    int cnt=n*k/2;
    while(cnt--){
        auto [a,b]=q.top();
        q.pop();
        res+=a;
        plusa[b].push_back(p2[b]);
        cnt2[b]++;
        p2[b]--;
        p1[b]--;
        if(p1[b]==-1)continue;
        q.push({d[b][p2[b]]+d[b][p1[b]],b});
    }
    for(int i=0;i<n;i++)for(int ii=0;ii<=p1[i];ii++)minusa[i].push_back(ii);
    //cout<<st1.size()<<" "<<st2.size()<<" "<<res<<"\n";
    //cout<<"pile -\n";
    //for(auto [a,b]:st1)cout<<"color: "<<a<<" value: "<<d[a][b]<<"\n";
    //cout<<"pile +\n";
    //for(auto [a,b]:st2)cout<<"color: "<<a<<" value: "<<d[a][b]<<"\n";
    vector<int>colors;for(int i=0;i<n;i++)colors.push_back(i);
    for(int step=0;step<k;step++){
        sort(colors.begin(),colors.end(),[](int a,int b){
            return cnt2[a]>cnt2[b];
        });
        for(int i=0;i<n/2;i++){
            int colorId=colors[i];
            int colorNum=plusa[colorId].back();
            plusa[colorId].pop_back();

            ans[colorId][colorNum]=step;
            cnt2[colorId]--;
        }

        for(int i=n/2;i<n;i++){
            int colorId=colors[i];
            int colorNum=minusa[colorId].back();
            minusa[colorId].pop_back();

            ans[colorId][colorNum]=step;
        }
    }
    allocate_tickets(ans);

    return res;
};


#define MULTITESTS false
void solve(int testCase){

}

void precalc(){

}
/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    precalc();
    int t=1;
    if(MULTITESTS)cin>>t;
    for(int i=1;i<=t;i++){
        auto t1=clock();
        solve(i);
        auto t2=clock();
        float delta=t2-t1;
        delta/=CLOCKS_PER_SEC;
        #ifdef LIS05ST
        cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
        #endif
    }
}*/

• 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