Submission #309162

#	Time	Username	Problem	Language	Result	Execution time	Memory
309162		knon0501	Carnival Tickets (IOI20_tickets)	C++14	16 / 100	973 ms	63504 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int L[1501];
queue<int> A[1501];
queue<int> B[1501];
int ss[1501];
queue<int> aa[1501];
queue<int> bb[1501];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer(n);
	int i,j;
	for(int i=0 ; i<n ; i++)answer[i].resize(m);
	long long ret=-1;
    if(k==m){
        vector<pair<int,pair<int,int>>> v;
        for(i=0 ; i<n ; i++){
            for(j=0 ; j<m ;j++){
                v.push_back({x[i][j],{i,j}});
            }
        }
        sort(v.begin(),v.end());
        long long ans=0;
        for(i=0 ; i<n/2*m ; i++){
            aa[v[i].second.first].push(v[i].second.first);
            ans-=v[i].first;
        }
        for(i=n/2*m ; i<n*m ; i++){
            bb[v[i].second.first].push(v[i].second.first);
            if(i>=(n+1)/2*m)ans+=v[i].first;
        }


        for(j=0 ; j<m ; j++){
            vector<pair<int,int>> vv;
            for(i=0 ; i<n ; i++)vv.push_back({bb[i].size(),i});
            sort(vv.begin(),vv.end());
            for(i=0 ; i<n/2 ; i++){
                answer[vv[i].second][aa[vv[i].second].front()]=j;
                aa[vv[i].second].pop();

            }
            for(i=n/2 ; i<n ; i++){
                answer[vv[i].second][bb[vv[i].second].front()]=j;
                bb[vv[i].second].pop();
            }
        }


        allocate_tickets(answer);
        return ans;
    }
	else if(k>=2){
        long long ans=0;
        int t=0;
        for(i=0 ; i<n ; i++){
            for(j=0 ; j<m ; j++){
                if(x[i][j])A[i].push(j);
                else B[i].push(j);
                answer[i][j]=-1;
                t+=x[i][j];
            }
        }
        for(i=0 ; i<n ; i++){
            for(j=0 ; j<m ;j++){
                if(x[i][j]==1){
                    L[i]=j-1;
                    break;
                }
            }
        }
        int y=m;
        for(i=m-1 ; i>=m-k ; i--){
            int cnt=-(n/2);
            for(j=0 ; j<n ; j++)cnt+=x[j][i];
            int s=0;

            vector<pair<int,int>> v;
            for(j=0 ; j<n ; j++)v.push_back({L[j],j});
            sort(v.rbegin(),v.rend());
            for(auto t: v){
                if(cnt>0 && t.first>=0 && x[t.second][i]){
                    x[t.second][t.first]=1;
                    L[t.second]--;
                    x[t.second][i]=0;
                    cnt--;
                }
            }
            for(j=0 ; j<n ; j++){
                if(x[j][i])s++;
            }
            ss[i]=s;
            if(cnt==0)y=i;

        }
        for(i=m-k ; i<m ; i++){
            for(j=0; j<n ; j++){
                if(ss[i]>(n+1)/2 && x[j][i]==1 && y<m && x[j][y]==0){
                    ss[y]++;
                    x[j][y++]=1;
                    x[j][i]=0;
                    ss[i]--;
                }
            }
            ans+=min(ss[i],n-ss[i]);
        }
        for(i=m-k ; i<m ; i++){
            for(j=0 ; j<n ; j++){
                if(x[j][i]){
                    answer[j][A[j].front()]=m-1-i;
                    A[j].pop();
                }
                else{
                    answer[j][B[j].front()]=m-1-i;
                    B[j].pop();
                }
            }
        }
        allocate_tickets(answer);
        return ans;
	}


	vector<int> aa,bb;
	pair<int,int> cc;
    for(i=0 ; i<n ; i++){
        int y=x[i][0];
        vector<pair<int,int>> a;
        vector<int> b,c;
        long long s=0;
        for(j=0 ; j<n ; j++){
            if(i==j)continue;
            if( x[j][0]>y){
                c.push_back(j);
            }
            else if(x[j][m-1]<y){
                b.push_back(j);
            }
            else{
                a.push_back({y-x[j][0]-(x[j][m-1]-y),j});
            }
        }
        sort(a.rbegin(),a.rend());
        if(c.size()>n/2 || b.size()>n/2)continue;
        for(auto t: a){
            if(b.size()<n/2)b.push_back(t.second);
            else c.push_back(t.second);
        }
        for(auto t: b)s+=y-x[t][0];
        for(auto t: c)s+=x[t][m-1]-y;
        if(s>ret){
            ret=s;
            cc={i,0};
            aa=b;
            bb=c;
        }
    }

    for(i=0 ; i<n ; i++){
        int y=x[i][m-1];
        vector<pair<int,int>> a;
        vector<int> b,c;
        long long s=0;
        for(j=0 ; j<n ; j++){
            if(i==j)continue;
            if( x[j][0]>y){
                c.push_back(j);
            }
            else if( x[j][m-1]<y){
                b.push_back(j);
            }
            else{
                a.push_back({y-x[j][0]-(x[j][m-1]-y),j});
            }
        }
        sort(a.rbegin(),a.rend());
        if(c.size()>n/2 || b.size()>n/2)continue;
        for(auto t: a){
            if(b.size()<n/2)b.push_back(t.second);
            else c.push_back(t.second);
        }
        for(auto t: b)s+=y-x[t][0];
        for(auto t: c)s+=x[t][m-1]-y;
        if(s>ret){
            ret=s;
            cc={i,m-1};
            aa=b;
            bb=c;
        }
    }

    for(i=0 ; i<n ; i++)for(j=0 ; j<m ; j++)answer[i][j]=-1;
    answer[cc.first][cc.second]=0;
    for(auto t: aa)answer[t][0]=0;
    for(auto t: bb)answer[t][m-1]=0;
	allocate_tickets(answer);
	return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:148:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:148:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:150:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~
tickets.cpp:181:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:181:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:183:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  183 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~

• Subtask 1: 0 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10