제출 #427004

#제출 시각아이디문제언어결과실행 시간메모리
427004zoooma13카니발 티켓 (IOI20_tickets)C++14
25 / 100
1302 ms99192 KiB
#include "bits/stdc++.h" #include "tickets.h" using namespace std; int n ,m ,k; vector <vector <int>> x; pair <int64_t ,vector <vector <int>>> construct(vector <int> pref){ //assert(pref.size() == n && accumulate(pref.begin() ,pref.end() ,0) == n*k/2); // vector <array <int ,3>> fh ,sh; // for(int i = 0; i < n; i++){ // for(int j = 0; j < pref[i]; j++) // fh.push_back({x[i][j] ,i ,j}); // for(int j = m-1; j >= m - (k-pref[i]); j--) // sh.push_back({x[i][j] ,i ,j}); // } vector <array <int ,3>> all; //{val ,color ,index} for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) all.push_back({x[i][j] ,i ,j}); sort(all.begin() ,all.end()); vector <array <int ,3>> fh{all.begin() ,all.begin() + (int)all.size()/2}; vector <array <int ,3>> sh{all.begin() + (int)all.size()/2 ,all.end()}; sort(fh.begin() ,fh.end() ,[](auto&i ,auto&j){ return i[1] < j[1]; }); sort(sh.begin() ,sh.end() ,[](auto&i ,auto&j){ return i[1] < j[1]; }); int64_t tot = 0; vector<vector<int>> answer(n ,vector<int>(m ,-1)); vector<bitset<1501>> taken(n); for(auto&bs : taken) bs.set(); int round_number = 0; for(auto&c : fh){ tot -= c[0]; answer[c[1]][c[2]] = round_number; taken[c[1]][round_number] = false; round_number = (round_number+1)%k; } vector <int> pos(n ,-1); for(auto&c : sh){ tot += c[0]; pos[c[1]] = taken[c[1]]._Find_next(pos[c[1]]); answer[c[1]][c[2]] = pos[c[1]]; } return {tot ,answer}; } long long find_maximum(int _k, vector<vector<int>> _x) { x = _x; n = x.size(); m = x[0].size(); k = _k; auto ans = construct({}); allocate_tickets(ans.second); return ans.first; }
#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...