Submission #831549

#	Time	Username	Problem	Language	Result	Execution time	Memory
831549		Dremix10	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	440 ms	79148 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);
    
    vector<int> c1,c2;
    int p1=-1,p2=-1;
    for(i=n-1;i>=n/2;i--){
        if(arr[i].mn == 0){
            p2 = i+1;
            p1 = i;
            break;
        }
        c1.push_back(arr[i].id);
    }
    if(p1 == p2){
        assert(p1 == -1);
        p1 = i;
        assert(i == n/2-1);
        p2 = i+1;
    }

    for(i=0;i<p2;i++){
        if(arr[i].mx == 0){
            p2 = i;
            p1 = i - 1;
            break;
        }
        c2.push_back(arr[i].id);

    }

    for(i=p2;i<n/2;i++){
        assert(arr[i].mn > 0);
        c1.push_back(arr[i].id);
    }
    /// p1 decreases, 

    /// p2 increases, 
    //assert(0);
    p2(1,1)
    assert(c1.size() + c2.size() == n);
    for(j=0;j<k;j++){
        p2(j,1)
        assert(c1.size() + c2.size() <= n);

        sum += min(c1.size(),c2.size());
        vector<int> n1,n2;
        set<int> s;
        pv(c1)
        pv(c2)

        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 && idx[arr[p1].id].size() > 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 && idx[arr[p2].id].size() > 0){
                    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;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from tickets.cpp:1:
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:95:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     assert(c1.size() + c2.size() == n);
      |            ~~~~~~~~~~~~~~~~~~~~~~^~~~
tickets.cpp:98:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         assert(c1.size() + c2.size() <= n);
      |                ~~~~~~~~~~~~~~~~~~~~~~^~~~

• 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