oj.uz

Submission #315701

# Submission time Handle Problem Language Result Execution time Memory
315701 2020-10-23T17:11:40 Z juggernaut Jousting tournament (IOI12_tournament) C++14
100 / 100
 51 ms 3320 KB 
/*
	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

*/

Compilation message

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 3 ms 1024 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2040 KB Output is correct
2 Correct 45 ms 3320 KB Output is correct
3 Correct 20 ms 2560 KB Output is correct
4 Correct 51 ms 3320 KB Output is correct
5 Correct 42 ms 3320 KB Output is correct
6 Correct 41 ms 3320 KB Output is correct
7 Correct 44 ms 3320 KB Output is correct
8 Correct 44 ms 3320 KB Output is correct
9 Correct 18 ms 2424 KB Output is correct
10 Correct 20 ms 2680 KB Output is correct