제출 #315701

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

tournament

/*
	Try to solve
    Solve it
    
    AND NEVER BACK TO THIS PROBLEM AGAIN
*/
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
const int Z=1<<17;
int nxt[Z],cnt[Z<<1],add[Z],res[Z];
int gt(int n){
	int x=1;
	while(x<Z){
		x<<=1;
		if(cnt[x]<n)n-=cnt[x++];
	}
	return x-Z;
}
void up(int x,int val){
	while(x){
		cnt[x]+=val;
		x>>=1;
	}
}
int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
    int i,tmp,x,y,sum=0,mx=-1,id;
	for(i=0;i<N;i++)nxt[i]=i+1,cnt[i+Z]=1;
	for(i=Z-1;i>=1;i--)cnt[i]=cnt[i<<1]+cnt[(i<<1)^1];
	for(i=0;i<C;i++){
		tmp=E[i]-S[i];
		S[i]=gt(S[i]+1);
		x=nxt[S[i]];
		while(tmp--){
			up(x+Z,-1);
			x=nxt[x];
		}
		E[i]=x-1;
		nxt[S[i]]=x;
	}
	for(i=1;i<N;i++)add[i]=add[i-1]+(K[i-1]>R);
	for(i=0;i<C;i++)if(add[E[i]]==add[S[i]])res[S[i]]++,res[E[i]]--;
	for(i=0;i<N;i++){
		sum+=res[i];
		if(mx<sum){
			mx=sum;
			id=i;
		}
	}
	return id;
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1

*/

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:30:17: warning: unused variable 'y' [-Wunused-variable]
   30 |     int i,tmp,x,y,sum=0,mx=-1,id;
      |                 ^
tournament.cpp:53:9: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  return id;
      |         ^~

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