제출 #429856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429856		Mounir	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	20 ms	1364 KiB

tournament

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = (1 << 18);
int nDebuts[N * 2];
int cumul[N];

bool onGagne(int fin, int deb){
	int sum = cumul[fin];
	if (deb > 0)
		sum -= cumul[deb - 1];
	return (sum == 0);
}

int getSum(int gauche, int droite){
	if (gauche > droite)
		return 0;
	if (gauche%2 == 1)
		return nDebuts[gauche] + getSum(gauche + 1, droite);
	if (droite%2 == 0)
		return nDebuts[droite] + getSum(gauche, droite - 1);
	return getSum(gauche / 2, droite / 2);
}

int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
	for (int iRound = 0; iRound < nRounds; ++iRound){
		int compression  = droite[iRound] - gauche[iRound];
		gauche[iRound] += getSum(N, N + gauche[iRound] - 1);
		droite[iRound] += getSum(N, N + droite[iRound]);
		for (int noeud = N + gauche[iRound]; noeud > 0; noeud /= 2)
			nDebuts[noeud] += compression;
	}

	for (int ind = 0; ind < nGars - 1; ++ind){
		cumul[ind] = (rangs[ind] > rangPaume);
		if (ind != 0)
			cumul[ind] += cumul[ind - 1];
	}

	for (int iRound = 0; iRound < nRounds; ++iRound){
		if (onGagne(gauche[iRound], droite[iRound])){
			cumul[gauche[iRound]]++;
			cumul[droite[iRound]]--;
		}
	}
	

	int iOpt = 0;
	for (int ind = 1; ind < nGars; ++ind){
		cumul[ind] += cumul[ind - 1];
		if (cumul[ind] > cumul[iOpt])
			iOpt = ind;
	}
	return iOpt;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51