Submission #698007

#	Time	Username	Problem	Language	Result	Execution time	Memory
698007		DJeniUp	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	589 ms	76132 KiB

tickets

#include "tickets.h"
#include "bits/stdc++.h"
#include <vector>

using namespace std;

typedef long long ll;
#define INF 100000000000007
typedef pair<int,int>pairll;
#define fr first
#define sc second
#define pb push_back

map<ll,ll>mp[1507];

vector<vector<int> >ans;
vector<vector<int> >v;

priority_queue<pairll>ql,qr,q;
ll res,l[1507],r[1507],n,m;

ll L(ll x){
    if(l[x]==0)return -INF;
    return v[x][r[x]]+v[x][l[x]-1];
}
ll R(ll x){
    if(r[x]==m-1)return -INF;
    return -v[x][l[x]]-v[x][r[x]+1];
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	n = x.size();
	m = x[0].size();
    
    if(k==m){
        ll res=0;
        for(int i=1;i<=n;i++){
            vector<int>ro;
            for(int j=0;j<m;j++){
                res+=x[i-1][j];
                ro.push_back(-1);
            }
            ans.push_back(ro);
            q.push({-x[i-1][0],i});
        }
        //exit(1);
        //cout<<q.size()<<endl;
        for(int i=1;i<=(n*m)/2;i++){
            //cout<<q.size()<<endl;
            if(q.size()>0){
                ll m1=q.top().fr;
                ll m2=q.top().sc;
                //cout<<m1<<" "<<m2<<" " <<rs[m2]<<endl;
                l[m2]++;
                q.pop();
                res+=m1*2;
                if(l[m2]<m)q.push({-x[m2-1][l[m2]],m2});
            }
        }
        //cout<<q.size()<<endl;
        //cout<<1<<endl;
        
        ll g=0;
        for(int i=n;i>=1;i--){
            //cout<<i<<" "<<rs[i]<<endl;
            ll h=g;
            
            //cout<<i<<" "<<rs[i]<<endl;
            for(int j=0;j<l[i];j++){
                //cout<<j<<" "<<h<<endl;
                ans[i-1][j]=(h%k);
                h++;
                //cout<<j<<" "<<h<<endl;
                //cout<<j<<" ";
            }
           // cout<<endl;
            g=h;
            for(int j=m-1;j>=m-(k-l[i]);j--){
                ans[i-1][j]=(h%k);
                h++;
                //cout<<j<<" "<<h<<endl;
                //cout<<j<<" ";
            }
            //cout<<endl;
        }
        allocate_tickets(ans);
        return res;
        
    }
    swap(v,x);
    for(int i=0;i<n;i++){
        vector<int>rs;
        rs.clear();
        for(int i=0;i<m;i++){
            rs.pb(-1);
        }
        ans.pb(rs);
        l[i]=(k+(i%2))/2;
        r[i]=m-(k+(i+1)%2)/2-1;
        for(int j=0;j<l[i];j++){
            res-=v[i][j];
        }
        for(int j=r[i]+1;j<m;j++){
            res+=v[i][j];
        }
        ql.push({L(i),i});
        qr.push({R(i),i});
        //cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;
    }
    
    while(1){
        while(ql.top().fr!=L(ql.top().sc))ql.pop();
        while(qr.top().fr!=R(qr.top().sc))qr.pop();
        ll m1=ql.top().sc;
        ll m2=qr.top().sc;
        if(L(m1)+R(m2)<=0)break;
        ql.pop();
        qr.pop();
        if(m1==m2){
            while(ql.top().fr!=L(ql.top().sc))ql.pop();
            while(qr.top().fr!=R(qr.top().sc))qr.pop();
            if(ql.size()==0 || qr.size()==0)break;
            ll m3=ql.top().sc;
            ll m4=qr.top().sc;
            ql.pop();
            qr.pop();
            if(L(m3)+R(m2)<=0 && L(m1)+R(m4)<=0)break;
            if(L(m3)+R(m2)>L(m1)+R(m4)){
                res+=L(m3)+R(m2);
                l[m3]--;
                r[m3]--;
                l[m2]++;
                r[m2]++;
                ql.push({L(m3),m3});
                qr.push({R(m2),m2});
                ql.push({L(m2),m2});
                qr.push({R(m3),m3});
                //ql.push({L(m1),m1});
                qr.push({R(m4),m4});
            }else{
                res+=L(m1)+R(m4);
                l[m1]--;
                r[m1]--;
                l[m4]++;
                r[m4]++;
                ql.push({L(m1),m1});
                qr.push({R(m4),m4});
                ql.push({L(m4),m4});
                qr.push({R(m1),m1});
                //ql.push({L(m1),m1});
                ql.push({L(m3),m3});
            }
        }else{
            res+=L(m1);
            res+=R(m2);
            l[m1]--;
            r[m1]--;
            l[m2]++;
            r[m2]++;
            ql.push({L(m1),m1});
            qr.push({R(m2),m2});
            ql.push({L(m2),m2});
            qr.push({R(m1),m1});
        }
    }
    
    ll g=0;
    for(int i=n-1;i>=0;i--){
        //cout<<i<<" "<<rs[i]<<endl;
        ll h=g;
        
        //cout<<i<<" "<<rs[i]<<endl;
        for(int j=0;j<l[i];j++){
            //cout<<j<<" "<<h<<endl;
            ans[i][j]=(h%k);
            h++;
            //cout<<j<<" "<<h<<endl;
            //cout<<j<<" ";
        }
       // cout<<endl;
        g=h;
        for(int j=m-1;j>=m-(k-l[i]);j--){
            ans[i][j]=(h%k);
            h++;
            //cout<<j<<" "<<h<<endl;
            //cout<<j<<" ";
        }
        //cout<<endl;
    }
    allocate_tickets(ans);
    
	return res;
}

• 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