Submission #1082435

#TimeUsernameProblemLanguageResultExecution timeMemory
1082435woodCarnival Tickets (IOI20_tickets)C++17
11 / 100
1 ms860 KiB
#include "tickets.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define vi vector<int> #define ll long long #define pb push_back #define eb emplace_back #define p32 pair<int,int> long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(), m = x[0].size(); vector<vi> ans; if(m==1){ vi p; for(int i = 0; i<n; i++){ ans.pb({0}); p.pb(x[i][0]);} sort(p.begin(),p.end()); ll sum = 0; for(int i =0; i<n; i++) sum+=abs(p[n/2]-p[i]); allocate_tickets(ans); return sum; } ll result = 0; bool finalchoice[n]; for(int i = 0; i<2*n; i++){ bool choice[n]; memset(choice,0,sizeof choice); //true if we pick the big card int mid = x[i%n][0]; if(i>=n){ mid = x[i%n][m-1]; choice[i] = true;} int lowcnt = 0,highcnt = 0; ll sum = 0; priority_queue<p32,vector<p32>,greater<>> q; for(int j = 0; j<n; j++){ if(i==j) continue; int a = x[j][0], b = x[j][m-1]; if(a>mid){ sum+=b-mid; highcnt++; choice[j] = true; } else if(b<mid){ sum+=mid-a; lowcnt++; } else if(mid-a>b-mid){ sum+=mid-a; lowcnt++; q.emplace(2*mid-a-b,j); } else{ sum+=b-mid; highcnt++; choice[j] = true; q.emplace(a+b-2*mid,j); } } while(highcnt>lowcnt&&!q.empty()) { int x = q.top().first, j = q.top().second; if(choice[j]){ sum-=x; highcnt--; lowcnt++; } q.pop(); } while(lowcnt>highcnt&&!q.empty()){ int x = q.top().first, j = q.top().second; if(!choice[j]){ sum-=x; highcnt++; lowcnt--; } q.pop(); } if(highcnt!=lowcnt) continue; if(sum>result){ for(int j = 0; j<n; j++) finalchoice[j] = choice[j]; } } ans.resize(n); fill(x.begin(),x.end(),vi(m,-1)); for(int i = 0; i<n; i++){ if(finalchoice[i]) x[i][m-1] = 0; else x[i][0] = 0; } allocate_tickets(ans); return result; }
#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...