Submission #380930

#	Time	Username	Problem	Language	Result	Execution time	Memory
380930		Pichon5	Carnival Tickets (IOI20_tickets)	C++17	14 / 100	639 ms	57824 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
long long find_maximum(int k,vector<vi> x) {
	int n = x.size();
	int m = x[0].size();
	ll res=0;
	vector<vi>M(n,vi(m,-1));
    vector<pair<int,int> >ind;
    vector<pair<int,int> >cant;//blanco y negro
    for(int i=0;i<n;i++)ind.pb({0,m-1});
    for(int i=0;i<n;i++){
        int a=0,b=0;
        for(int l=0;l<m;l++){
            if(x[i][l]==0){
                a++;
            }else{
                b++;
            }
        }
        cant.pb({a,b});
    }
    vi v;
    vector<pair<int,int>  >E;
    for(int i=0;i<k;i++){
        v.clear();
        E.clear();
        int a=0,b=0,aux=0;
        for(int l=0;l<n;l++){
            if(cant[l].S==0){
                a++;
                M[l][ind[l].F]=i;
                ind[l].F++;
                continue;
            }
            if(cant[l].F==0){
                b++;
                M[l][ind[l].S]=i;
                ind[l].S--;
                continue;
            }
            v.pb(l);
            E.pb({cant[l].F,l});
        }
        if(a>=n/2 or b>=n/2){
            for(int l=0;l<v.size();l++){
                int num=v[l];
                if(a>b){
                    b++;
                    M[num][ind[num].S]=i;
                    ind[num].S--;
                    cant[num].S--;
                }else{
                    a++;
                    M[num][ind[num].F]=i;
                    ind[num].F++;
                    cant[num].F--;
                }
            }
        }else{
            sort(E.begin(),E.end());
            int I=E.size()-1;
            for(int l=a;l<n/2;l++){
                int num=E[I].S;
                M[num][ind[num].F]=i;a++;
                ind[num].F++;cant[num].F--;
                I--;
            }
            I=0;
            for(int l=b;l<n/2;l++){
                int num=E[I].S;b++;
                M[num][ind[num].S]=i;
                    ind[num].S--;
                    cant[num].S--;
                    I++;
            }
        }
        res+=min(a,b);
    }
    allocate_tickets(M);
	return res;
}
/*
0 0 0 1
0 1 1 1
0 0 0 0
1 1 1 1

*/

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int l=0;l<v.size();l++){
      |                         ~^~~~~~~~~
tickets.cpp:37:21: warning: unused variable 'aux' [-Wunused-variable]
   37 |         int a=0,b=0,aux=0;
      |                     ^~~

• 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