Submission #471279

#	Time	Username	Problem	Language	Result	Execution time	Memory
471279		Cross_Ratio	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	616 ms	52688 KiB

tickets

#include <bits/stdc++.h>
//#include "tickets.h"
using namespace std;

void allocate_tickets(vector<vector<int>>);

typedef pair<int,int> P;

long long find_maximum(int k, vector<vector<int> > x) {
    int N = x.size();
    int M = x[0].size();
    vector<vector<int> > ans;
    ans.resize(N);
    int i,j;
    for(i=0;i<N;i++) {
        ans[i].resize(M);
        fill(ans[i].begin(),ans[i].end(),-1);
    }
	long long int cnt = 0;
	if(k==1) {
        vector<int> pt1;
        vector<int> pt2;
        pt1.resize(N);
        pt2.resize(N);
        fill(pt2.begin(),pt2.end(),M-1);
        int j, st;
        for(j=0;j<k;j++) {
            vector<P> V;
            for(i=0;i<N;i++) {
                V.push_back(P(x[i][pt2[i]]+x[i][pt1[i]],i));
            }
            sort(V.begin(),V.end());
            for(i=0;i<N;i++) {
                int n = V[i].second;
                if(i < N / 2) {
                    ans[n][pt1[n]] = j;
                    cnt -= x[n][pt1[n]];
                    pt1[n]++;
                }
                else {
                    ans[n][pt2[n]] = j;
                    cnt += x[n][pt2[n]];
                    pt2[n]--;
                }
            }
        }
        allocate_tickets(ans);
        return cnt;
	}
	else if(k == M) {
        vector<P> A;
        for(i=0;i<N;i++) {
            for(j=0;j<M;j++) {
                A.push_back(P(x[i][j],M*i+j));
            }
        }
        sort(A.begin(),A.end());
        vector<int> V, C;
        V.resize(N);
        C.resize(N);
        vector<vector<bool> > vis;
        vis.resize(N);
        for(i=0;i<N;i++) vis[i].resize(M);
        for(i=0;i<N*M/2;i++) {
            int na = A[i].second;
            int t1 = na / M;
            int t2 = na % M;
            while(C[V[t1]] == N / 2) V[t1]++;
            C[V[t1]]++;
            ans[t1][t2] = V[t1];
            vis[t1][V[t1]] = true;
            V[t1]++;
            cnt -= A[i].first;
        }
        V.clear();
        V.resize(N);
        for(i=N*M/2;i<N*M;i++) {
            int na = A[i].second;
            int t1 = na / M;
            int t2 = na % M;
            while(C[V[t1]] == N||vis[t1][V[t1]]) V[t1]++;
            C[V[t1]]++;
            ans[t1][t2] = V[t1];
            V[t1]++;
            cnt += A[i].first;
        }
        allocate_tickets(ans);
        return cnt;
	}
	else {
        vector<P> A;
        A.resize(N);
        for(i=0;i<N;i++) {
            for(j=0;j<M;j++) {
                A[i].first += x[i][j];
            }
            A[i].second = i;
        }
        vector<int> pt1;
        vector<int> pt2;
        pt1.resize(N);
        pt2.resize(N);
        fill(pt2.begin(),pt2.end(),M-1);
        sort(A.begin(),A.end(),[](P x, P y) {return x.first > y.first;});
        for(i=0;i<k;i++) {
            for(j=0;j<N;j++) {
                if(j < N/2) {
                    ans[A[j].second][pt2[A[j].second]] = i;
                    cnt += x[A[j].second][pt2[A[j].second]];
                    A[j].first -= x[A[j].second][pt2[A[j].second]];
                    pt2[A[j].second]--;
                }
                else {
                    ans[A[j].second][pt1[A[j].second]] = i;
                    cnt -= x[A[j].second][pt1[A[j].second]];
                    A[j].first -= x[A[j].second][pt1[A[j].second]];
                    pt1[A[j].second]++;
                }
            }
            sort(A.begin(),A.end(),[](P x, P y) {return x.first > y.first;});
        }
        allocate_tickets(ans);
        return cnt;
	}
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:26:16: warning: unused variable 'st' [-Wunused-variable]
   26 |         int j, st;
      |                ^~

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