제출 #1013370

#제출 시각아이디문제언어결과실행 시간메모리
1013370d4xn팀들 (IOI15_teams)C++17
21 / 100
225 ms524288 KiB
#pragma GCC optimize ("Ofast") #include "teams.h" #include <bits/stdc++.h> using namespace std; const int N = 100000, S = 1000; int n; pair<int, int> sg[N]; vector<pair<int, int>> lp[N]; bitset<N> curr, temp, bt[N], pre[N/S + 1]; void init(int nn, int a[], int b[]) { n = nn; for (int i = 0; i < n; i++) { sg[i] = make_pair(b[i], a[i]); } sort(sg, sg+n); for (int i = 0; i < n; i++) { lp[sg[i].second].push_back(make_pair(sg[i].first, i)); } priority_queue<pair<int, int>> pq; for (int i = 1; i <= n; i++) { for (auto& [j, idx] : lp[i]) { pq.push(make_pair(-j, idx)); curr[idx] = 1; } bt[i] = curr; while (!pq.empty() && -pq.top().first <= i) { curr[pq.top().second] = 0; pq.pop(); } } pre[0].reset(); for (int i = 1; i < N/S + 1; i++) { pre[i] = pre[i-1]; for (int j = S*(i-1); j < S*i; j++) { pre[i][j] = 1; } } } int can(int m, int k[]) { sort(k, k+m); curr = pre[N/S]; for (int i = S*(N/S); i <= n; i++) { curr[i] = 1; } for (int i = 0; i < m; i++) { temp = (curr & bt[k[i]]); if (((int)temp.count()) < k[i]) return 0; // solo quiero los k primeros de temp int l = 0; int r = n-1; while (l < r) { int mid = (l+r) >> 1; int block = mid/S; for (int j = S*block; j <= mid; j++) { pre[block][j] = 1; } if (((int)(temp & pre[block]).count()) >= k[i]) r = mid; else l = mid+1; for (int j = S*block; j <= mid; j++) { pre[block][j] = 0; } } // le quito a curr los k primeros de temp int block = l/S; for (int j = S*block; j <= l; j++) { pre[block][j] = 1; } curr ^= (temp & pre[block]); for (int j = S*block; j <= l; j++) { pre[block][j] = 0; } } return 1; } /* cerr << i << endl; for (int j = 0; j < n; j++) { cerr << curr[j] << " "; } cerr << endl; cerr << k[i] << endl; for (int j = 0; j < n; j++) { cerr << bt[k[i]][j] << " "; } cerr << endl; temp = curr & bt[k[i]]; cerr << (int)temp.count() << endl << endl; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...