제출 #831496

#제출 시각아이디문제언어결과실행 시간메모리
831496Dremix10카니발 티켓 (IOI20_tickets)C++17
0 / 100
455 ms69280 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define F first #define S second #define all(x) (x).begin(),(x).end() const int N = 3e5+5; const int MOD = 1e9+7; const ll INF = 1e18+5; #ifdef dremix #define p2(x,y) cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<endl; #define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl; #else #define p2(x,y) {} #define ppv(x) {} #endif struct ano{ int mn,mx,id; bool operator<(const ano &o)const{ return mn < o.mn; } }; long long find_maximum(int k, vector<vector<int> > x) { int n = x.size(); int m = x[0].size(); int i,j; vector<vector<vector<int> > > idx(n,vector<vector<int> >(2,vector<int>())); ano arr[n]; vector<vector<int> > answer(n,vector<int>(m,-1)); ll sum = 0; for (i = 0; i < n; i++) { arr[i] = {0,0,0}; for(j=0;j<n;j++){ if(x[i][j]) arr[i].mx ++; else arr[i].mn ++; arr[i].id = i; idx[i][x[i][j]].push_back(j); } } //sort(all(arr)); sort(arr,arr+n); vector<int> c1,c2; for(i=n/2;i<n;i++) c1.push_back(arr[i].id); for(i=0;i<n/2;i++) c2.push_back(arr[i].id); int p1 = n/2-1; /// p1 decreases, int p2 = n/2; /// p2 increases, for(j=0;j<k;j++){ sum += min(c1.size(),c2.size()); vector<int> n1,n2; set<int> s; for(auto v : c1){ answer[v][idx[v][0].back()] = j; idx[v][0].pop_back(); if(idx[v][0].empty()){ n2.push_back(v); if(p1 >= 0){ n1.push_back(arr[p1].id); s.insert(arr[p1].id); p1--; } } else{ n1.push_back(v); } } for(auto v : c2){ answer[v][idx[v][1].back()] = j; idx[v][1].pop_back(); if(s.count(v)){ s.erase(v); } else if(idx[v][1].empty()){ n1.push_back(v); if(p2 < n){ n2.push_back(arr[p2].id); s.insert(arr[p2].id); p2++; } } else{ n2.push_back(v); } } c2 = n2; c1.clear(); for(auto v : n1){ if(!s.count(v)){ c1.push_back(v); } } } allocate_tickets(answer); return sum; }
#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...