Submission #874340

#TimeUsernameProblemLanguageResultExecution timeMemory
874340MatjazJousting tournament (IOI12_tournament)C++14
100 / 100
68 ms5576 KiB
#include <vector> #include <algorithm> #include <iostream> using namespace std; // Insight: each S[i] E[i] corresponds to some interval in the original set of positions // The interval only matters if your player is in it - and there is a unique answer as to whether it wins or loses // You can find the best position with a sweep. // Does linked list + fenwick tree work? vector<int> tree; int N; int sum(int x){ int s = 0; x++; while (x > 0){ s += tree[x]; x -= x & (-x); } return s; } int find(int x){ int l = 0; int u = N - 1; while (l < u){ int mid = l + (u - l) / 2; //cout << mid << " " << sum(mid) << endl; if (sum(mid) < x) l = mid + 1; else u = mid; } return l; } void update(int x,int v){ x++; while (x <= tree.size()){ tree[x] += v; x += x & (-x); } } int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) { N = _N; vector<int> s(N+1); s[0] = 0; for (int i=1;i<=N;i++) s[i] = s[i-1] + (K[i-1] > R); vector<int> next(N); for (int i=0;i<N;i++) next[i] = i + 1; vector<pair<int,int> > sweep_events; tree.assign(N + 2, 0); for (int i=0;i<N;i++) update(i, 1); for (int i=0;i<C;i++){ int left = find(S[i] + 1); int right = find(E[i] + 1); //We can put in assert(left is active) int tmp = left; while (tmp != right){ tmp = next[tmp]; update(tmp, -1); } next[left] = next[right]; right = next[left] - 1; //cout << S[i] << " " << E[i] << " " << left << " " << right << endl; if (s[right] - s[left] == 0){ sweep_events.push_back(make_pair(left, 1)); sweep_events.push_back(make_pair(right + 1, -1)); } } sort(sweep_events.begin(), sweep_events.end()); int best_position = 0; int best_wins = 0; int wins = 0; for (int i=0;i<sweep_events.size();i++){ wins += sweep_events[i].second; if (wins > best_wins){ best_wins = wins; best_position = sweep_events[i].first; } } return best_position; }

Compilation message (stderr)

tournament.cpp: In function 'void update(int, int)':
tournament.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     while (x <= tree.size()){
      |            ~~^~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i=0;i<sweep_events.size();i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...