제출 #300397

#제출 시각아이디문제언어결과실행 시간메모리
300397easrui카니발 티켓 (IOI20_tickets)C++14
0 / 100
4 ms640 KiB
#include "tickets.h" #include <bits/stdc++.h> #define va first #define vb second #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<pii,int> ppi; typedef pair<int,pii> pip; const int MN = 1505; const int MOD = 1e9+7; const int INF = 1e9; vector<pii> T; int a[MN],s[MN],cur[MN],D[MN],U[MN]; int n,m; int cal(int x) { return D[x]+1+m-U[x]; } bool cmp(int x, int y) { return s[x]<s[y]; } ll find_maximum(int k, vector<vector<int>> x) { n = x.size(); m = x[0].size(); ll sum = 0; vector<vector<int>> ans; vector<int> row(m,-1); for(int i=0; i<n; i++){ ans.push_back(row); } for(int i=0; i<n; i++) for(int j=0; j<m; j++) T.emplace_back(x[i][j],i); sort(all(T)); int s=0, e=n*m-1; for(int i=0; i<n; i++){ D[i] = -1; U[i] = m; } while(s<n*k/2){ D[T[s].vb]++; s++; } while(e>=n*m-n*k/2){ U[T[e].vb]--; e--; } int cnt = 0; priority_queue<pip> PQ; for(int i=0; i<n; i++){ PQ.emplace(cal(i),pii{i,cnt}); cur[i] = cnt++; } while(PQ.top().va>k){ int q = PQ.top().vb.va; bool flag = 0; if(U[q]>=m||D[q]>=0&&T[s].va-x[q][D[q]]<x[q][U[q]]-T[e].va) flag = 1; if(flag){ D[q]--; PQ.emplace(cal(q),pii{q,cnt}); cur[q] = cnt++; D[T[s].vb]++; PQ.emplace(cal(T[s].vb),pii{T[s].vb,cnt}); cur[T[s].vb] = cnt++; s++; } else{ U[q]++; PQ.emplace(cal(q),pii{q,cnt}); cur[q] = cnt++; U[T[e].vb]--; PQ.emplace(cal(T[e].vb),pii{T[e].vb,cnt}); cur[T[e].vb] = cnt++; e--; } while(PQ.top().vb.vb!=cur[PQ.top().vb.va]) PQ.pop(); } vector<int> v(n); for(int i=0; i<k; i++){ for(int j=0; j<n; j++) v[j] = D[j]; sort(all(v)); for(int j=0; j<n; j++){ if(D[j]>=v[n/2]){ ans[j][D[j]] = i; sum -= x[j][D[j]]; D[j]--; } else{ ans[j][U[j]] = i; sum += x[j][U[j]]; U[j]++; } } } return sum; }

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:69:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |         if(U[q]>=m||D[q]>=0&&T[s].va-x[q][D[q]]<x[q][U[q]]-T[e].va) flag = 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...