Submission #307036

#	Time	Username	Problem	Language	Result	Execution time	Memory
307036		knon0501	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	1032 ms	63480 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];
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;
        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:108:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:108:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:110:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~
tickets.cpp:141:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |            ~~~~~~~~^~~~
tickets.cpp:141:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  141 |         if(c.size()>n/2 || b.size()>n/2)continue;
      |                            ~~~~~~~~^~~~
tickets.cpp:143:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |             if(b.size()<n/2)b.push_back(t.second);
      |                ~~~~~~~~^~~~

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