Submission #864786

#	Time	Username	Problem	Language	Result	Execution time	Memory
864786		andrei_boaca	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	382 ms	60344 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
int nr1[1505],take[1505],my0[1505],my1[1505],l[1505],r[1505];
bool comp(pll a, pll b)
{
    return a.second>b.second;
}
bool by1(int a,int b)
{
    return nr1[a]>nr1[b];
}
bool bytake(int a,int b)
{
    return my1[a]>my1[b];
}
long long find_maximum(int k, std::vector<std::vector<int>> vectoras) {
	n = vectoras.size();
	m = vectoras[0].size();
	sol=vectoras;
    v=vectoras;
    bool sub3=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            sol[i][j]=-1;
            if(v[i][j]>1)
                sub3=0;
        }
    if(k==1)
    {
        vector<pll> a;
        for(int i=0;i<n;i++)
        {
            sol[i][0]=0;
            ans-=v[i][0];
            a.push_back({i,v[i][m-1]+v[i][0]});
        }
        sort(a.begin(),a.end(),comp);
        for(int i=0;i<n/2;i++)
        {
            ll poz=a[i].first;
            ans+=v[poz][0]+v[poz][m-1];
            sol[poz][0]=-1;
            sol[poz][m-1]=0;
        }
        allocate_tickets(sol);
        return ans;
    }
    if(sub3)
    {
        vector<int> linii;
        for(int i=0;i<n;i++)
        {
            linii.push_back(i);
            for(int j=0;j<m;j++)
                nr1[i]+=v[i][j];
        }
        sort(linii.begin(),linii.end(),by1);
        int suma=0;
        for(int i:linii)
        {
            int val=min(nr1[i],k);
            val=min(val,k*n/2-suma);
            take[i]=val;
            suma+=val;
        }
        reverse(linii.begin(),linii.end());
        suma=0;
        for(int i:linii)
        {
            int val=min(m-nr1[i],k-take[i]);
            val=min(val,k*n/2-suma);
            suma+=val;
            int lft=k-take[i]-val;
            take[i]+=lft;
        }
        for(int i=0;i<n;i++)
        {
            ans+=take[i];
            my1[i]=take[i];
            my0[i]=k-take[i];
            l[i]=0;
            r[i]=m-1;
        }
        if(ans>k*n/2)
        {
            int dif=ans-k*n/2;
            ans-=2*dif;
        }
        for(int pas=0;pas<k;pas++)
        {
            linii.clear();
            for(int i=0;i<n;i++)
                linii.push_back(i);
            sort(linii.begin(),linii.end(),bytake);
            int p1=-1,p0=n;
            for(int z=0;z<n;z++)
            {
                int i=linii[z];
                if(my1[i]>0)
                    p1=max(p1,z);
                if(my0[i]>0)
                    p0=min(p0,z);
            }
            if(p1<n/2-1)
            {
                for(int z=0;z<n;z++)
                {
                    int i=linii[z];
                    if(i<=p1)
                    {
                        my1[i]--;
                        sol[i][r[i]]=pas;
                        r[i]--;
                    }
                    else
                    {
                        my0[i]--;
                        sol[i][l[i]]=pas;
                        l[i]++;
                    }
                }
                continue;
            }
            if(p0>n/2)
            {
                for(int z=0;z<n;z++)
                {
                    int i=linii[z];
                    if(i>p0)
                    {
                        my1[i]--;
                        sol[i][r[i]]=pas;
                        r[i]--;
                    }
                    else
                    {
                        my0[i]--;
                        sol[i][l[i]]=pas;
                        l[i]++;
                    }
                }
                continue;
            }
            for(int z=0;z<n;z++)
            {
                int i=linii[z];
                if(i<n/2)
                {
                    my1[i]--;
                    sol[i][r[i]]=pas;
                    r[i]--;
                }
                else
                {
                    my0[i]--;
                    sol[i][l[i]]=pas;
                    l[i]++;
                }
            }
            continue;
        }
        allocate_tickets(sol);
        return ans;
    }
	return 1;
}

• 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