Submission #557181

#TimeUsernameProblemLanguageResultExecution timeMemory
557181czhang2718Carnival Tickets (IOI20_tickets)C++17
16 / 100
749 ms89684 KiB
#include "tickets.h" #include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=a; i<=b; i++) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) #define pb push_back typedef vector<int> vi; typedef pair<int,int> pii; #define f first #define s second const int N=1501; bool use[N][N]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row(m, -1); answer.push_back(row); } vector<int> cnt(n); vector<pii> inc; rep(i,0,n-1){ rep(j,0,k-1){ inc.pb({x[i][m-1-j]+x[i][k-1-j], i}); use[i][j]=1; } } sort(all(inc), greater<pii>()); rep(t,1,n*k/2){ auto p=inc[t-1]; // cout << "switch " << p.s << " " << k-1-cnt[p.s] << "->" << m-1-cnt[p.s] << '\n'; use[p.s][m-1-cnt[p.s]]=1; use[p.s][k-1-cnt[p.s]]=0; cnt[p.s]++; } vector<pair<int, pii>> vec; rep(i,0,n-1) rep(j,0,m-1){ if(use[i][j]) vec.pb({x[i][j], {i,j}}); } sort(all(vec)); long long sum=0; rep(i,1,n*k){ if(i<=n*k/2) sum-=vec[i-1].f; else sum+=vec[i-1].f; } auto L=vec[n*k/2]; vector<vi> big(n), small(n); vi v[3]; rep(i,0,n-1){ rep(j,0,m-1){ if(!use[i][j]) continue; if(make_pair(x[i][j], make_pair(i,j))>=L) big[i].pb(j); else small[i].pb(j); } if(sz(big[i]) && sz(small[i])) v[2].pb(i); else if(sz(big[i])) v[1].pb(i); else v[0].pb(i); } rep(t,0,k-1){ int a=0, b=0; vi put_back; // small int A=sz(v[0]); rep(i,1,min(A,n/2)){ a++; int j=v[0].back(); v[0].pop_back(); answer[j][small[j].back()]=t; small[j].pop_back(); if(sz(small[j])) put_back.pb(j); } for(int i:put_back) v[0].pb(i); // big put_back.clear(); int B=sz(v[1]); rep(i,1,min(B,n/2)){ b++; int j=v[1].back(); v[1].pop_back(); answer[j][big[j].back()]=t; big[j].pop_back(); if(sz(big[j])) put_back.pb(j); } for(int i:put_back) v[1].pb(i); // both put_back.clear(); rep(i,1,n/2-a){ int j=v[2].back(); v[2].pop_back(); answer[j][small[j].back()]=t; small[j].pop_back(); if(sz(small[j]) && sz(big[j])) put_back.pb(j); else if(sz(small[j])) v[0].pb(j); else v[1].pb(j); } rep(i,1,n/2-b){ int j=v[2].back(); v[2].pop_back(); answer[j][big[j].back()]=t; big[j].pop_back(); if(sz(small[j]) && sz(big[j])) put_back.pb(j); else if(sz(small[j])) v[0].pb(j); else v[1].pb(j); } for(int i:put_back) v[2].pb(i); } allocate_tickets(answer); return sum; } // dont know what to do without you
#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...