Submission #747112

#	Time	Username	Problem	Language	Result	Execution time	Memory
747112		Rafi22	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	696 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000002022;
int inf=1000000007;
ll infl=1000000000000000007;

/*void allocate_tickets(vector<vector<int>>r)
{
    int n=sz(r),m=sz(r[0]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) cout<<r[i][j]<<" ";
        cout<<endl;
    }
}*/

ll find_maximum(int k,vector<vector<int>>a)
{
    int n=sz(a),m=sz(a[0]);
    vector<pair<int,pair<int,int>>>V;
    vector<vector<int>>r(n,vector<int>(m,-1));
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) V.pb({a[i][j],{i,j}});
        for(int j=m-k;j<m;j++) sum+=a[i][j];
    }
    sort(all(V));
    set<pair<int,pair<int,int>>>good,bad;
    ll ans=-infl,act=0;
    int ile=n*k/2,ii,jj;
    for(auto [q,p]:V)
    {
        int i=p.st,j=p.nd;
        if(j<k)
        {
            act+=-a[i][j]-a[i][m-k+j];
            good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
        }
        if(j>=m-k)
        {
            ile--;
            if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
            {
                bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
                act+=-a[i][j]-a[i][j-m+k];
            }
        }
        if(ile<0) break;
        while(sz(good)>ile)
        {
            act-=(*good.begin()).st;
            bad.insert(*good.begin());
            good.erase(*good.begin());
        }
        while(sz(bad)>0&&sz(good)<ile)
        {
            act+=(*--bad.end()).st;
            good.insert(*--bad.end());
            bad.erase(*--bad.end());
        }
        if(sz(good)==ile&&act>ans)
        {
            ans=act;
            ii=i;
            jj=j;
        }
    }
    good.clear(),bad.clear();
    ile=n*k/2;
    vector<int>X(n,-1),Y(n,m-k);
    for(auto [q,p]:V)
    {
        int i=p.st,j=p.nd;
        if(j<k)
        {
            good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
        }
        if(j>=m-k)
        {
            ile--;
            X[i]++;
            Y[i]--;
            if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
            {
                bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
            }
        }
        if(ile<0) break;
        while(sz(good)>ile)
        {
            act-=(*good.begin()).st;
            bad.insert(*good.begin());
            good.erase(*good.begin());
        }
        while(sz(bad)>0&&sz(good)<ile)
        {
            act+=(*--bad.end()).st;
            good.insert(*--bad.end());
            bad.erase(*--bad.end());
        }
        if(i==ii&&j==jj)
        {
            for(auto x:good)
            {
                X[x.nd.st]++;
                Y[x.nd.st]++;
            }
            break;
        }
    }
    for(int j=0;j<k;j++)
    {
        int c1=n/2,c2=n/2;
        for(int i=0;i<n;i++)
        {
            if(X[i]==-1)
            {
                c2--;
                r[i][Y[i]]=j;
                Y[i]++;
            }
            else if(Y[i]==m)
            {
                c1--;
                r[i][X[i]]=j;
                X[i]--;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(X[i]!=-1&&c1>0)
            {
                c1--;
                r[i][X[i]]=j;
                X[i]--;
            }
            else
            {
                c2--;
                r[i][Y[i]]=j;
                Y[i]++;
            }
        }
    }
    allocate_tickets(r);
    return ans+sum;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [q,p]:V)
      |              ^
tickets.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [q,p]:V)
      |              ^
tickets.cpp:112:17: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |         if(i==ii&&j==jj)
      |            ~~~~~^~~~~~~
tickets.cpp:112:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |         if(i==ii&&j==jj)
      |         ^~

• Subtask 1: 11 / 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