제출 #430513

#제출 시각아이디문제언어결과실행 시간메모리
430513JeanBombeur마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
22 ms1108 KiB
#include <iostream> #include <cstdio> #include <vector> using namespace std; // <|°_°|> 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) { sum += Fenwick[ans + i]; ans += i; } } 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); } int ans = 0; for (int i = 0; i < nbRounds; i ++) { Left[i] ++, Right[i] ++; int maxRang = -1, maxDP = -1; vector <int> pos; for (int j = Left[i]; j < Right[i]; j ++) { pos.push_back(FindFirst(j)); } for (int a : pos) { maxRang = max(maxRang, Rang[a]); maxDP = max(maxDP, NbVictoires[a]); } maxDP ++; if (maxRang > nouvRang) maxDP = -1; for (int a : pos) { Add(a, -1); NbVictoires[a] = -1; } Add(pos[0], 1); NbVictoires[pos[0]] = maxDP; ans = max(ans, maxDP); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...