Submission #831683

#	Time	Username	Problem	Language	Result	Execution time	Memory
831683		Dremix10	Carnival Tickets (IOI20_tickets)	C++17	14 / 100	473 ms	72628 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
    #define p2(x,y) cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v<<", ";cerr<<endl;
#else
    #define p2(x,y) {}
    #define ppv(x) {}
    #define pv(x) {}
#endif



struct ano{
    int mn,mx,id;
    bool operator<(const ano &o)const{
        return mn < o.mn;
    }
};

long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	
    
    int i,j;
    vector<vector<vector<int> > > idx(n,vector<vector<int> >(2,vector<int>()));
    ano arr[n];

    vector<vector<int> > answer(n,vector<int>(m,-1));
    ll sum = 0;

	for (i = 0; i < n; i++) {
        arr[i] = {0,0,0};
        for(j=0;j<m;j++){
            if(x[i][j])
                arr[i].mx ++;
            else
                arr[i].mn ++;
            arr[i].id = i;
            idx[i][x[i][j]].push_back(j);
        }
	}
    //sort(all(arr));

    sort(arr,arr+n);

    for(j=0;j<k;j++){
        vector<bool> v(n,true);
        int cnt[2] = {};
        for(i=0;i<n;i++){
            int id = arr[i].id;

            if(idx[id][0].empty()){
                answer[id][idx[id][1].back()] = j;
                cnt[1]++;
                idx[id][1].pop_back();
            }
            else if(idx[id][1].empty()){
                answer[id][idx[id][0].back()] = j;
                cnt[0]++;
                idx[id][0].pop_back();
            }
            else{
                v[i] = false;
            }

        }
        for(i=n-1;i>=0;i--){
            if(cnt[0] >= n/2)break;
            if(v[i])continue;
            //cnt[0] ++;
            int id = arr[i].id;
            answer[id][idx[id][0].back()] = j;
            cnt[0]++;
            idx[id][0].pop_back();
            v[i] = true;
        }
        for(i=0;i<n;i++){
            if(v[i])continue;
            //cnt[1] ++;
            int id = arr[i].id;
            answer[id][idx[id][1].back()] = j;
            cnt[1]++;
            idx[id][1].pop_back();
        }
        pv(cnt)
        sum += min(cnt[0],cnt[1]);
    }
    

	allocate_tickets(answer);
	return sum;
}

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