Submission #1229165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229165		a4n_	Carnival Tickets (IOI20_tickets)	C++20	11 / 100	14 ms	25928 KiB

tickets

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, m, k, a[1505][1505], mark[N], pl[1505], pr[1505], res[1505][1505];
ll cnt[N], visi[1505][1505];
vector<ll> hlp[N];
long long find_maximum(int _k, vector<vector<int>> d) {
    k = _k, n = size(d), m = size(d[0]);
    
    priority_queue<pll> pq1;
    priority_queue<pll> pq2;

    for(int i=1; i<=n; i++) {
        // pl[i] = 1, pr[i] = m;
        for(int j=1; j<=m; j++) {
            a[i][j] = d[i-1][j-1];
            res[i][j] = -1;
        }
        sort(a[i] + 1, a[i] + m + 1);

        if(i <= n / 2) {
            pl[i] = k + 1, pr[i] = m;
            pq1.push({a[i][pl[i]-1] + a[i][pr[i]], i});
            // for(int j=1; j<=k; j++) res[i][j] = j-1;
        } else {
            pl[i] = 1, pr[i] = m - k;
            pq2.push({- a[i][pr[i]+1] - a[i][pl[i]], i});
            // for(int j=m-k+1; j<=m; j++) res[i][j] = j-(m-k+1);
        }
    }

    while(pq1.top().F + pq2.top().F > 0) {
        pll v1 = pq1.top(), v2 = pq2.top();
        pq1.pop(), pq2.pop();

        pl[v1.S] --, pr[v1.S] --;
        pq1.push({a[v1.S][pl[v1.S]-1] + a[v1.S][pr[v1.S]], v1.S});
        
        pl[v2.S] ++, pr[v2.S] ++;
        pq2.push({- a[v2.S][pr[v2.S]+1] - a[v2.S][pl[v2.S]], v2.S});
        
        // int t1 = res[v1.S][pl[v1.S]], t2 = res[v2.S][pr[v2.S]];
        // res[v1.S][pl[v1.S]] = -1;
        // res[v2.S][pr[v2.S]] = -1;
        // res[v2.S][pl[v2.S]-1] = t1;
        // res[v1.S][pr[v1.S]+1] = t2;
    }

    int ptr = 0;
    for(int i=1; i<=n; i++) {
        // cout<<pl[i]<< " ==> "<<pr[i]<<endl;
        for(int j=1; j<pl[i]; j++) {
            cnt[ptr] --;
            res[i][j] = ptr;
            visi[i][ptr] = 1;
            ptr = MOD(ptr + 1, k);
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=pr[i]+1; j<=m; j++) {
            cnt[ptr] ++;
            while(visi[i][ptr] == 1) ptr ++;
            visi[i][ptr] = 1;
            res[i][j] = ptr;
            ptr = MOD(ptr + 1, k);
        }
    }


    // for(int i=1; i<=n; i++) {
    //     for(int j=1; j<pl[i]; j++) res[i][j]
    // }

    // for(int tc=1; tc<=k; tc ++) {
    //     vector<pll> vec;
    //     fill(mark, mark+n+2, 0);
    //     for(int j=1; j<=n; j++) {
    //         vec.pb({ -a[j][pl[j]] - a[j][pr[j]], j});
    //     }
    //     sort(all(vec));
    //     reverse(all(vec));
    //     for(int i=0; i<n/2; i++) {
    //         mark[vec[i].S] = 1;
    //     }
    //     for(int i=1; i<=n; i++) {
    //         if(mark[i] == 1) {
    //             res[i][pl[i]] = tc - 1;
    //             pl[i] ++;
    //         } else  {
    //             res[i][pr[i]] = tc - 1;
    //             pr[i] --;
    //         }
    //     }
    // }
    
    ll ans = 0;
    vector<vector<int>> tmp;
    for(int i=1; i<=n; i++) {
        tmp.pb({});
        for(int j=1; j<=m; j++) tmp.back().pb(res[i][j]);
        for(int j=1; j<=m; j++) {
            if(res[i][j] >= 0) hlp[res[i][j]].pb(a[i][j]);
        }
    }
    allocate_tickets(tmp);

    for(int i=0; i<k; i++) {
        sort(all(hlp[i]));
        ll mid = hlp[i][n/2];
        for(auto it : hlp[i]) {
            ans += abs(mid - it);
        }
    }
    return ans;
}

// void allocate_tickets( std::vector<std::vector<int>> _x);

• 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