Submission #419364

#	Time	Username	Problem	Language	Result	Execution time	Memory
419364		cpp219	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	17 ms	27256 KiB

tickets

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include "tickets.h"
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1500 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
long long kq;
ll n,m,k;
multiset<LL> ms[N];
set<LL> sMin,sMax; /// val   id

void Repack(){
    sMin.clear(); sMax.clear();
    for (ll i = 0;i < n;i++){
        LL L = *ms[i].begin(),R = *ms[i].rbegin();
        sMin.insert({L.fs,i});
        sMax.insert({R.fs,i});
    }
}

long long find_maximum(ll k, vector<vector<ll>> a){
    n = a.size();
    for (ll i = 0;i < n;i++){
        for (ll j = 0;j < a[i].size();j++){
            ll now = a[i][j];
            ms[i].insert({now,j});
        }
    }
    Repack();
    vector<vector<ll>> ans;
    ans.resize(N);
    for (ll i = 0;i < ans.size();i++){
        ans[i].resize(N);
        for (ll j = 0;j < ans[i].size();j++) ans[i][j] = -1;
    }
    for (ll id = 1;id <= k;id++){
        ll big,sm;
        ll take = n/2;
        while(take--){

            LL p = *sMax.rbegin(); sMax.erase(p);
            LL now = *ms[p.sc].rbegin(); ms[p.sc].erase(*ms[p.sc].rbegin());
            ans[p.sc][now.sc] = id; big = p.fs;
            LL cur = *ms[p.sc].begin();
            cur.sc = p.sc; sMin.erase(cur);
            //cout<<cur.fs<<" "<<cur.sc<<" x ";
            //cout<<sMax.size()<<" "<<sMin.size()<<"\n\n";

            p = *sMin.begin(); sMin.erase(p);
            now = *ms[p.sc].begin(); ms[p.sc].erase(ms[p.sc].begin());
            ans[p.sc][now.sc] = id; sm = p.fs; //cout<<p.sc<<"\n";
            cur = *ms[p.sc].rbegin();
            cur.sc = p.sc; sMax.erase(cur);
            //cout<<big<<" "<<sm<<"\n";
            kq += (long long) big - sm;
        }
        Repack(); //exit(0);
    }
    allocate_tickets(ans);
    return kq;
}

Compilation message (stderr)

tickets.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
tickets.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (ll j = 0;j < a[i].size();j++){
      |                       ~~^~~~~~~~~~~~~
tickets.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (ll i = 0;i < ans.size();i++){
      |                   ~~^~~~~~~~~~~~
tickets.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (ll j = 0;j < ans[i].size();j++) ans[i][j] = -1;
      |                       ~~^~~~~~~~~~~~~~~

• 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