Submission #1005442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005442		hasan2006	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	559 ms	117660 KiB

tickets

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

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 2009;
int b[2009][N] = {},c[N] = {};
deque<int>d[N][3];
ll find_maximum(int k, vector<vector<int>> a){
    ll i , j , l , r , s  = 0,sum = 0,  f , x , y , m , n;
    n = a.size();
    m = a[0].size();
    vector<pair<int,pair<int,int>>>v;
    for(i = 0; i < n; i++){
        for(j = 0; j < k; j++){
            sum -= a[i][j];
            b[i][j] = 1;
            v.pb({a[i][m - 1 - j] + a[i][k - 1 - j], {i , -j}});
        }
    }
    vector<vector<int>>vc(n);
    for(i = 0; i < n; i++)
        vc[i].resize(m , -1);
    sort(rall(v));
    for(i = 0; i < v.size() / 2; i++){
        sum += v[i].fi;
        v[i].se.se *= -1;
        if(b[v[i].se.fi][k - 1 - v[i].se.se] == 1)
            b[v[i].se.fi][k - 1 - v[i].se.se] = 0;
        b[v[i].se.fi][m - 1 - v[i].se.se] = 2;
    }
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            d[i][b[i][j]].pb(j);
    for(x = 0; x < k; x++){
        vector<pair<int,int>>dq;
        for(i = 0; i < n; i++)
            dq.pb({d[i][1].size() ,i });
        sort(rall(dq));
        for(i = 0; i < n; i++){
            y = dq[i].se;
            f = (i < n / 2 ? 1 : 2);
            vc[y][d[y][f].front()] = x;
            d[y][f].pop_front();
        }
    }
    allocate_tickets(vc);
    return sum;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(i = 0; i < v.size() / 2; i++){
      |                ~~^~~~~~~~~~~~~~
tickets.cpp:24:16: warning: unused variable 'l' [-Wunused-variable]
   24 |     ll i , j , l , r , s  = 0,sum = 0,  f , x , y , m , n;
      |                ^
tickets.cpp:24:20: warning: unused variable 'r' [-Wunused-variable]
   24 |     ll i , j , l , r , s  = 0,sum = 0,  f , x , y , m , n;
      |                    ^
tickets.cpp:24:24: warning: unused variable 's' [-Wunused-variable]
   24 |     ll i , j , l , r , s  = 0,sum = 0,  f , x , y , m , n;
      |                        ^

• 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