Submission #318365

#	Time	Username	Problem	Language	Result	Execution time	Memory
318365		katearima	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	678 ms	51892 KiB

tickets

#include "tickets.h"
#include <vector>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
int i,j,n,m,k;
long long sum;
pair<int,int> p;
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
long long find_maximum(int k, vector<vector<int> > x) {
	n = x.size();
	m = x[0].size();
	vector<vector<int> > ans;
	vector<int> row(m,-1),f(n),v(n);
	for (int i = 0; i < n; i++) ans.push_back(row);
	for(i=0; i<n; i++){
		for(j=m-k; j<m; j++){
			ans[i][j]=-2;
			sum+=x[i][j];
		}
	}
	for(i=0; i<n; i++){
		int y=x[i][0]+x[i][m-k];
		pq.push(make_pair(y,i));
	}
	int y=n*k/2;

	while(y--){
		int a=pq.top().first; int b=pq.top().second;
		if(f[b]>=k){
			pq.pop();
			a=pq.top().first;
			b=pq.top().second;
		}
		ans[b][m-k+v[b]]=-1; ans[b][v[b]]=-3;
		
		f[b]++; v[b]++;
		int c=v[b];
		sum-=a;
		if(m-k+c!=m&&c!=m)pq.push(make_pair(x[b][c]+x[b][m-k+c],b));
		pq.pop();	
	}
	vector<vector<int> > pos(n),neg(n);
    for(i=0; i<n; i++){
    	for(j=0;j<m; j++){
    		if(ans[i][j]==-3){
    			neg[i].push_back(j);
			}
			if(ans[i][j]==-2){
				pos[i].push_back(j);
			}
		}
	}
	int t=k;
	
	while(t--){
		vector<int> v(n);
		int g=0;
		for(i=0; i<pos.size(); i++){
			if(pos[i].size()<=1) continue;
			if(g==n/2) break;
		    int h=pos[i].back();
		    ans[i][h]=t;
		    pos[i].pop_back();
		    g++;
		    v[i]=1;
		}
		if(g!=n/2){
			for(i=0; i<pos.size(); i++){
				if(pos[i].size()!=1||v[i]==1) continue;
				if(g==n/2) break;
		    	int h=pos[i].back();
		    	ans[i][h]=t;
		    	pos[i].pop_back();
				g++;
				v[i]=1;
			}
		}
		g=0;
		for(i=0; i<neg.size(); i++){      
			if(neg[i].size()<=1|| v[i]==1) continue;
			if(g==n/2) break;
		    int h=neg[i].back();
		    ans[i][h]=t;
		    //cout<<i<<" "<<h<<endl;
		    neg[i].pop_back();
		    g++;
		    v[i]=1;
		}
		if(g!=n/2){
			for(i=0; i<neg.size(); i++){
				if(neg[i].size()!=1||v[i]==1) continue;
				if(g==n/2) break;
		    	int h=neg[i].back();
		    	ans[i][h]=t;
		    	//cout<<i<<" "<<h<<endl;
		    	neg[i].pop_back();
				g++;
			}
		}
		v.clear();
	}

	allocate_tickets(ans);
	return sum;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(i=0; i<pos.size(); i++){
      |            ~^~~~~~~~~~~
tickets.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(i=0; i<pos.size(); i++){
      |             ~^~~~~~~~~~~
tickets.cpp:80:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(i=0; i<neg.size(); i++){
      |            ~^~~~~~~~~~~
tickets.cpp:91:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for(i=0; i<neg.size(); i++){
      |             ~^~~~~~~~~~~

• 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