Submission #1215680

#TimeUsernameProblemLanguageResultExecution timeMemory
1215680cpdreamerCarnival Tickets (IOI20_tickets)C++17
25 / 100
662 ms84416 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = (ll)1e9+7; #define P pair #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() long long find_maximum(int k, std::vector<std::vector<int>> x) { int n=(int)x.size(); int m=(int)x[0].size(); V<V<int>>ans(n,V<int>(m,-1)); int h=n/2; V<P<int,P<int,int>>>vp; for (int i=0;i<n;i++) { for (int j=0;j<m;j++) { vp.pb({x[i][j],{i,j}}); } } sort(all(vp)); ll a=0; for (int i=0;i<h*m;i++) { a-=vp[i].F; } for (int i=h*m;i<n*m;i++) { a+=vp[i].F; } V<P<int,V<int>>>v(n,{0,V<int>(m,1)}); V<int>id(n,0); V<P<int,int>>v1; for (int i=0;i<h*m;i++) { v[vp[i].S.F].S[id[vp[i].S.F]]=0; v[vp[i].S.F].F++; id[vp[i].S.F]++; } for (int i=0;i<n;i++) { v1.pb({v[i].F,i}); } sort(all(v1)); reverse(all(v1)); V<int>l; for (int i=0;i<h;i++) { for (int j=0;j<m;j++) { l.pb(j); } } int ind=0; for (int i=0;i<n;i++) { int col=v1[i].S; for (int j=0;j<m;j++) { if (v[col].S[j]==0) { ans[col][j]=l[ind]; ind++; } } } for (int i=0;i<n;i++) { int col=v1[i].S; set<int>st; for (int j=0;j<m;j++) { st.insert(j); } for (int j=0;j<m;j++) { if (v[col].S[j]==0) { st.erase(ans[col][j]); } } for (int j=0;j<m;j++) { if (v[col].S[j]==1) { ans[col][j]=*st.begin(); st.erase(st.begin()); } } } allocate_tickets(ans); return a; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...