Submission #307020

#	Time	Username	Problem	Language	Result	Execution time	Memory
307020		knon0501	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	940 ms	53480 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];
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>=2){
        long long ans=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;
            }
        }
        for(i=0 ; i<n ; i++){
            for(j=0 ; j<m ;j++){
                if(x[i][j]==1){
                    L[i]=j-1;
                    break;
                }
            }
        }

        for(i=m-1 ; i>=m-k ; i--){

            int cnt=-(n+1)/2;
            for(j=0 ; j<n ; j++)cnt+=x[j][i];
            int s=0;


            for(j=0 ; j<n ; j++){
                if(cnt>0 && L[j]>=0 && x[j][i]){
                    x[j][L[j]]=1;
                    L[j]--;
                    x[j][i]=0;
                    cnt--;
                }
                if(x[j][i]){
                    answer[j][A[j].front()]=m-1-i;
                    A[j].pop();
                    s++;
                }
                else{
                    answer[j][B[j].front()]=m-1-i;
                    B[j].pop();
                }
            }
            ans+=min(s,n-s);
        }
        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:86:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:86:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:88:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~
tickets.cpp:119:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:119:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:121:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~

• Subtask 1: 11 / 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