Submission #800488

#	Time	Username	Problem	Language	Result	Execution time	Memory
800488		I_Love_EliskaM_	Carnival Tickets (IOI20_tickets)	C++14	25 / 100	503 ms	72488 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;

ll find_maximum(int k, vector<vector<int>>a) {
    int n=a.size(), m=a[0].size();
    if (m==1) {
        vector<int> v; forn(i,n) v.pb(a[i][0]);
        sort(all(v));
        ll ans=0;
        forn(i,n/2) ans+=v[i+n/2]-v[i];
        vector<vector<int>> z(n,vector<int>(m,0));
        allocate_tickets(z);
        return ans;
    }
    int Z=0;for(auto&x:a)for(auto&y:x)Z=max(Z,y);
    if (Z<=1) {

        vector<int> s(n);
        forn(i,n) forn(j,m) s[i]+=a[i][j];
        
        int ans=0;
        
        vector<vector<int>> rans(n,vector<int>(m,-1));
        vector<vector<int>> one(n), zero(n);
        
        forn(i,n) forn(j,m) if (a[i][j]) one[i].pb(j); else zero[i].pb(j);

        forn(r,k) {

            vector<pi> v2;
            forn(i,n) v2.pb({s[i],i});
            sort(all(v2));
            vector<int> para(n);
            forn(i,n/2) {
                int x=v2[i].s, y=v2[n-1-i].s;
                para[x]=y, para[y]=x;
            }

            vector<int> vis(n);
            vector<int> v;

            int forced=0;

            forn(i,n) {
                if (vis[i]) continue;
                if (zero[i].size() && one[para[i]].size()) {
                    continue;
                } 

                if (one[i].size() && zero[para[i]].size()) {
                    continue;
                } 

                if (zero[i].size() && zero[para[i]].size()) {
                    int x=zero[i].back(), y=zero[para[i]].back();
                    zero[i].pop_back(); zero[para[i]].pop_back();
                    rans[i][x]=r, rans[para[i]][y]=r;
                    vis[para[i]]=vis[i]=1;
                    v.pb(0); v.pb(0);
                    forced--;
                    continue;
                }

                if (one[i].size() && one[para[i]].size()) {
                    int x=one[i].back(), y=one[para[i]].back();
                    one[i].pop_back(); one[para[i]].pop_back();
                    rans[i][x]=r, rans[para[i]][y]=r;
                    vis[para[i]]=vis[i]=1;
                    v.pb(1); v.pb(1);
                    --s[i], --s[para[i]];
                    forced++;
                    continue;
                }

                assert(0);
            }

            forn(i,n) {
                if (vis[i]) continue;
                vis[i]=1;

                if (forced>0 && zero[i].size() && zero[para[i]].size()) {
                    int x=zero[i].back(), y=zero[para[i]].back();
                    zero[i].pop_back(); zero[para[i]].pop_back();
                    rans[i][x]=r, rans[para[i]][y]=r;
                    vis[para[i]]=1;
                    v.pb(0); v.pb(0);
                    --forced;
                    continue;
                }

                if (forced<0 && one[i].size() && one[para[i]].size()) {
                    int x=one[i].back(), y=one[para[i]].back();
                    one[i].pop_back(); one[para[i]].pop_back();
                    rans[i][x]=r, rans[para[i]][y]=r;
                    vis[para[i]]=1;
                    v.pb(1); v.pb(1);
                    --s[i], --s[para[i]];
                    ++forced;
                    continue;
                }

                if (s[i] <= s[para[i]]) {
                    if (zero[i].size() && one[para[i]].size()) {
                        int x=zero[i].back(), y=one[para[i]].back();
                        zero[i].pop_back(); one[para[i]].pop_back();
                        rans[i][x]=r, rans[para[i]][y]=r;
                        vis[para[i]]=1;
                        --s[para[i]];
                        v.pb(0); v.pb(1);
                        continue;
                    } 

                    if (one[i].size() && zero[para[i]].size()) {
                        int x=one[i].back(), y=zero[para[i]].back();
                        one[i].pop_back(); zero[para[i]].pop_back();
                        rans[i][x]=r, rans[para[i]][y]=r;
                        vis[para[i]]=1;
                        --s[i];
                        v.pb(0); v.pb(1);
                        continue;
                    }
                } else {
                    if (one[i].size() && zero[para[i]].size()) {
                        int x=one[i].back(), y=zero[para[i]].back();
                        one[i].pop_back(); zero[para[i]].pop_back();
                        rans[i][x]=r, rans[para[i]][y]=r;
                        vis[para[i]]=1;
                        --s[i];
                        v.pb(0); v.pb(1);
                        continue;
                    }

                    if (zero[i].size() && one[para[i]].size()) {
                        int x=zero[i].back(), y=one[para[i]].back();
                        zero[i].pop_back(); one[para[i]].pop_back();
                        rans[i][x]=r, rans[para[i]][y]=r;
                        vis[para[i]]=1;
                        --s[para[i]];
                        v.pb(0); v.pb(1);
                        continue;
                    }
                }

                assert(0);
            }
            sort(all(v));
            forn(i,n/2) ans+=v[i+n/2]-v[i];

        }
        allocate_tickets(rans);
        return ans;

    }
    return 0;
}

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