Submission #831496

#	Time	Username	Problem	Language	Result	Execution time	Memory
831496		Dremix10	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	455 ms	69280 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.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;
#else
    #define p2(x,y) {}
    #define ppv(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<n;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);
    
    vector<int> c1,c2;

    for(i=n/2;i<n;i++)
        c1.push_back(arr[i].id);

    for(i=0;i<n/2;i++)
        c2.push_back(arr[i].id);

    int p1 = n/2-1;
    /// p1 decreases, 
    int p2 = n/2;
    /// p2 increases, 
    
    for(j=0;j<k;j++){
        sum += min(c1.size(),c2.size());
        vector<int> n1,n2;
        set<int> s;

        for(auto v : c1){
            answer[v][idx[v][0].back()] = j;
            idx[v][0].pop_back();
            if(idx[v][0].empty()){
                n2.push_back(v);
                if(p1 >= 0){
                    n1.push_back(arr[p1].id);
                    s.insert(arr[p1].id);
                    p1--;
                }
            }
            else{
                n1.push_back(v);
            }
        }

        for(auto v : c2){
            answer[v][idx[v][1].back()] = j;
            idx[v][1].pop_back();
            if(s.count(v)){
                s.erase(v);
            }
            else if(idx[v][1].empty()){
                n1.push_back(v);
                if(p2 < n){
                    n2.push_back(arr[p2].id);
                    s.insert(arr[p2].id);
                    p2++;
                }
            }
            else{
                n2.push_back(v);
            }
        }

        c2 = n2;
        c1.clear();
        for(auto v : n1){
            if(!s.count(v)){
                c1.push_back(v);
            }
        }

    }
    

	allocate_tickets(answer);
	return sum;
}
    

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