Submission #1078927

#TimeUsernameProblemLanguageResultExecution timeMemory
1078927Faisal_SaqibCarnival Tickets (IOI20_tickets)C++17
11 / 100
40 ms856 KiB
#include "tickets.h" #include <vector> #include <bits/stdc++.h> using namespace std; #define ll long long ll find_ans(vector<int> cur) { sort(begin(cur),end(cur)); vector<ll> pre={0}; for(auto i:cur) pre.push_back(pre.back()+(ll)i); ll mi=2e18; int n=cur.size(); for(int i=0;i<n;i++) { ll x=cur[i]; mi=min(mi,(x*i)-pre[i] + (pre[n]-pre[i])-((x*(n-i)))); } return mi; } long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); if(k==1) { vector<pair<int,pair<int,int>>> pos; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { pos.push_back({x[i][j],{i,j}}); } } sort(begin(pos),end(pos)); auto ans=x; ll cost=-1; { vector<int> used(n,0); int l=0; int r=pos.size(); r--; vector<vector<int>> cur_ans; for(int i=0;i<n;i++) { cur_ans.push_back({}); for(int j=0;j<m;j++) { cur_ans[i].push_back(-1); } } vector<int> cur; for(int i=0;i<n;i++) { while(l<=r) { if(used[pos[r].second.first]) r--; else break; } while(l<=r) { if(used[pos[l].second.first]) l++; else break; } int val=pos[l].first; int col=pos[l].second.first; int var=pos[r].first; int cor=pos[r].second.first; cur.push_back(val); int anp=find_ans(cur); cur.pop_back(); cur.push_back(var); int bnp=find_ans(cur); cur.pop_back(); if(anp<=bnp) { cur.push_back(val); cur_ans[col][pos[l].second.second]=0; used[col]=1; } else { cur.push_back(var); cur_ans[cor][pos[r].second.second]=0; used[cor]=1; } } if(find_ans(cur)>cost) { ans=cur_ans; cost=find_ans(cur); } } allocate_tickets(ans); return cost; } else { map<int,int> cnt[n]; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cnt[i][x[i][j]]++; } } for(int i=0;i<k;i++) { for(int can=(n/2);can>=0;can--) { } } } std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row(m); for (int j = 0; j < m; j++) { if (j < k) { row[j] = j; } else { row[j] = -1; } } answer.push_back(row); } allocate_tickets(answer); return 1; }
#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...