제출 #430582

#제출 시각아이디문제언어결과실행 시간메모리
430582JeanBombeur마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
17 ms2760 KiB
#include <iostream> #include <cstdio> #include <vector> using namespace std; // <|°_°|> const int INFINI = (1000 * 1000 * 1000); const int MAX_CHEVALIERS = (100 * 1000); const int LOG = (16); int NbVictoires[MAX_CHEVALIERS]; int Fenwick[MAX_CHEVALIERS]; void Add(int id, int val) { for (int i = id; i < MAX_CHEVALIERS; i |= (i + 1)) { Fenwick[i] += val; } return; } int FindFirst(int nb) { int ans = -1; int sum = 0; for (int i = (1 << LOG); i > 0; i >>= 1) { if (ans + i < MAX_CHEVALIERS && sum + Fenwick[ans + i] < nb) { ans += i; sum += Fenwick[ans]; } } return ans + 1; } int GetBestPosition(int nbChevaliers, int nbRounds, int nouvRang, int *Rang, int *Left, int *Right) { for (int i = 0; i < nbChevaliers; i ++) { NbVictoires[i] = 0; Add(i, 1); } pair <int, int> ans = {0, 0}; for (int i = 0; i < nbRounds; i ++) { Left[i] ++, Right[i] ++; vector <int> pos; for (int j = Left[i]; j <= Right[i]; j ++) { pos.push_back(FindFirst(j)); } int maxRang = -1; pair <int, int> maxDP = {-1, 0}; for (int a : pos) { if (a != pos.back()) maxRang = max(maxRang, Rang[a]); if (NbVictoires[a] > maxDP.first) maxDP = {NbVictoires[a], a}; } maxDP.first ++; if (maxRang > nouvRang) maxDP.first = - INFINI; for (int a : pos) { if (a != maxDP.second) { Add(a, -1); NbVictoires[a] = - INFINI; } } if (pos.back() != nbChevaliers - 1) maxRang = max(maxRang, Rang[pos.back()]); if (maxDP.second == nbChevaliers - 1) return 69420; Rang[maxDP.second] = maxRang; NbVictoires[maxDP.second] = maxDP.first; if (maxDP.first > ans.first || (maxDP.first == ans.first && maxDP.second < ans.second)) { ans = make_pair(maxDP.first, maxDP.second); } } printf("%d %d\n", ans.first, ans.second); return ans.second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...