제출 #241352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241352		kshitij_sodani	마상시합 토너먼트 (IOI12_tournament)	C++17	0 / 100	1092 ms	2040 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
//#include "tournament.h"

int tree[110001];
int aa[100001];
int bb[100001];
int n;
void u(int i,int j){
	while(i<110001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
int s(int i){
	int su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int find(int x){
/*	int ind=0;
	int su=0;
	for(int i=19;i>=0;i--){
		if((1<<i)+ind<=n){
			if(su+tree[ind+(1<<i)]<=x){
				ind+=(1<<i);
				su+=tree[ind];
			}
		}
	}*/
	int ind;
	for(int i=0;i<n+1;i++){
		if(s(i)==x){
			ind=i;
		}
	}
	return ind;
}
int find2(int x){
	/*int ind=0;
	int su=0;
	for(int i=19;i>=0;i--){
		if((1<<i)+ind<=n){
			if(su+tree[ind+(1<<i)]<x){
				ind+=(1<<i);
				su+=tree[ind];
			}
		}
	}
	if(s(ind+1)!=x){
		while(true){
			continue;
		}
	}*/
	for(int i=0;i<n+1;i++){
		if(s(i)==x){
			return i;
			
		}
	}
	//return ind+1;
}
int tree2[110001];
void u2(int i,int j){
	while(i<110001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int s2(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int tree3[400001];
int kk[100001];
void build(int no,int l,int r){
	if(l==r){
		tree3[no]=kk[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree3[no]=max(tree3[no*2+1],tree3[no*2+2]);
	}
}
int query(int no,int l,int r,int aa,int bb){
	if(r<aa or bb<l){
		return 0;
	}
//	cout<<l<<':'<<r<<endl;
	if(aa<=l and r<=bb){
		return tree3[no];
	}
	int mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int GetBestPosition(int nn, int c, int r, int k[], int ss[], int tt[]) {
	n=nn;
	if(n==1){
		while(true){
			continue;
		}
	}
	for(int i=0;i<n;i++){
		u(i+1,1);
	}
	for(int i=0;i<n-1;i++){
		kk[i]=k[i];
	}
	build(0,0,n-2);
/*	int arr[n];
	for(int i=0;i<n;i++){
		arr[i]=0;

	}*/
	int ma=0;
	for(int j=0;j<c;j++){
		aa[j]=find2(ss[j]+1);

		bb[j]=find(tt[j]+1);
		for(int i=ss[j]+1;i<=tt[j];i++){
			u(i+1,-1);
		}
	//	cout<<aa[j]<<","<<bb[j]<<endl;
		if(j==c-1 and (aa[j]!=1 or bb[j]!=n)){
			while(true){
				continue;
			}
		}
		aa[j]-=1;
		bb[j]-=2;
	//	int x=0;

	//	cout<<aa[j]<<","<<bb[j]<<endl;
	//	cout<<endl;


		if(query(0,0,n-2,aa[j],bb[j])<r){
		//	cout<<j<<endl;
			u2(aa[j]+1,1);
			u2(bb[j]+3,-1);
	//		cout<<aa[j]+1<<"::"<<bb[j]+2<<endl;
		}

	}
	int mi=-1;
	int ind=0;
	for(int i=0;i<n;i++){
		int x=s2(i+1);
	//	cout<<i<<"::"<<x<<","<<ind<<endl;
		if(x>mi){
			mi=x;
			ind=i;
		}
	}


	return ind;
}

/*
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:130:6: warning: unused variable 'ma' [-Wunused-variable]
  int ma=0;
      ^~
tournament.cpp: In function 'int find2(int)':
tournament.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
tournament.cpp: In function 'int find(int)':
tournament.cpp:46:9: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ind;
         ^~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:145:8: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   bb[j]-=2;
   ~~~~~^~~

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