Submission #393585

#	Time	Username	Problem	Language	Result	Execution time	Memory
393585		Hazem	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1091 ms	11260 KiB

tournament

#include <bits/stdc++.h>
//#include "grader.h"

using namespace std;
 
#define S second
#define F first
#define LL long long 
 
const int N1 = 4e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;

int sizes[N1],par[N1],mx[N1];
int tree[N1],val[N1],nxt[N1],pos[N1];
vector<int>vec[N1];

int find_set(int a){
	
	if(a==par[a])
		return a;
	else 
		return par[a] = find_set(par[a]);
}

void merge_set(int u,int v){
	
	u = find_set(u);
	v = find_set(v);
	
	if(u==v)return ;
	
	if(sizes[u]<sizes[v])swap(u,v);
	sizes[u] += sizes[v];
	par[v] = u;	
	mx[u] = max(mx[u],mx[v]);
	nxt[u] = max(nxt[u],nxt[v]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

	int n = N;
	for(int i=1;i<n;i++)
		val[i] = K[i-1];

	val[n] = R;
	
	for(int i = 1;i<=n;i++)
		sizes[i] = 1,par[i] = i,mx[i] = val[i],nxt[i] = i+1;
		
	for(int i=0;i<C;i++){
			
		int l = S[i]+1,r = E[i]+1;
		int cnt = 0;
		for(int j=1;j<=n;j++){
			if(find_set(j)!=find_set(j-1)){
				cnt++;
				if(cnt>=l&&cnt<=r)
					vec[i].push_back(j);
			}
			j = nxt[find_set(j)]-1;
		}
		for(int j=0;j<vec[i].size()-1;j++)
			merge_set(vec[i][j],vec[i][j+1]);
	}

	int cur = n;
	int curans = 0,curret = n-1;
	while(cur--){
		
		for(int i = 1;i<=n;i++)
			sizes[i] = 1,par[i] = i,mx[i] = val[i],nxt[i] = i+1;

		int ret = 0;
		for(int i=0;i<C;i++){
			for(int j=0;j<vec[i].size()-1;j++)
				merge_set(vec[i][j],vec[i][j+1]);

		int u = find_set(vec[i][0]);
		if(mx[u]==R)ret++;
		}
		if(ret>=curans)curans = ret,curret = cur;
		swap(val[cur],val[cur+1]);
	}
	return curret;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j=0;j<vec[i].size()-1;j++)
      |               ~^~~~~~~~~~~~~~~~
tournament.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for(int j=0;j<vec[i].size()-1;j++)
      |                ~^~~~~~~~~~~~~~~~

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