Submission #419371

#	Time	Username	Problem	Language	Result	Execution time	Memory
419371		cpp219	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	904 ms	78408 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,big[N],sm[N],C[N];
vector<vector<ll>> ans;
priority_queue<LL,vector<LL>,greater<LL>> pq;

void out(){
    for (ll i = 0;i < n;i++){
        for (ll j = 0;j < m;j++) cout<<ans[i][j]<<" ";
        cout<<"\n";
    }
    exit(0);
}

long long find_maximum(ll k, vector<vector<ll>> a){
    n = a.size(); m = a[0].size();
    vector<LL> B;
    ans.resize(n);
    for (ll i = 0;i < ans.size();i++){
        ans[i].resize(m);
        for (ll j = 0;j < ans[i].size();j++) ans[i][j] = -1;
        for (ll j = m - k;j < ans[i].size();j++){
            kq += a[i][j];
            B.push_back({a[i][j] + a[i][j - (m - k)],i});
        }

    }
    ll cnt = n*k/2;
    sort(B.begin(),B.end());
    for (ll i = 0;i < cnt;i++) kq -= B[i].fs,C[B[i].sc]++;
    ll l = 0;
    for (ll i = 0;i < n;i++){
        ll lim = C[i];
        for (ll j = 0;j < lim;j++) ans[i][j] = l++%k;
        ll r = l,j = m - 1,rm = k - C[i];
        while(rm--) ans[i][j] = r++%k,j--;
    }
    //out();
    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:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (ll i = 0;i < ans.size();i++){
      |                   ~~^~~~~~~~~~~~
tickets.cpp:33:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (ll j = 0;j < ans[i].size();j++) ans[i][j] = -1;
      |                       ~~^~~~~~~~~~~~~~~
tickets.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (ll j = m - k;j < ans[i].size();j++){
      |                           ~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10