Submission #393579

#	Time	Username	Problem	Language	Result	Execution time	Memory
393579		Hazem	Jousting tournament (IOI12_tournament)	C++14	17 / 100	1094 ms	2152 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],sum[N1],lasttaken[N1],mx[N1];
int tree[N1],val[N1],nxt[N1];

void update(int v,int l,int r,int pos,int val){
	
	if(l==r){
		tree[v] = val;
		return ;
	}
	
	int mid = (l+r)/2;
	
	if(pos<=mid)
		update(v*2,l,mid,pos,val);
	else 
		update(v*2+1,mid+1,r,pos,val);
		
	tree[v] = max(tree[v*2],tree[v*2+1]);
	
}

/*
int get(int v,int tl,int tr,int l,int r,int pos){
	
	if(tl>=l&&tr<=r)
		return tree[v];
	
	if(tl>r||tr<l)
		return -INF;
	
}
*/

pair<int,int> find_set(int a){
	
	if(a==par[a])
		return make_pair(a,sum[a]);
	else {
		pair<int,int>p = find_set(par[a]);
		sum[a] += p.S-lasttaken[a];
		par[a] = p.F;
		lasttaken[a] = sum[p.F];
		return make_pair(p.F,sum[a]);
	}
}

void merge_set(int u,int v){
	
	u = find_set(u).F;
	v = find_set(v).F;
	
	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]);
}

void add(int u){
		
	u = find_set(u).F;
	sum[u]++;
	lasttaken[u]++;
}

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;
			
	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++){
			
			int l = S[i]+1,r = E[i]+1;
		
			vector<int>vec;
			int cnt = 0;
			for(int j=1;j<=n;j++){
				if(find_set(j).F!=find_set(j-1).F){
					cnt++;
					if(cnt>=l&&cnt<=r)
						vec.push_back(j);
				}
				j = nxt[find_set(j).F]-1;
			}
		
			for(int j=0;j<vec.size()-1;j++)
				merge_set(vec[j],vec[j+1]);	
			
			int u = find_set(vec[0]).F;
			//printf("%d ",mx[u]);
			if(mx[u]==R)ret++;
		}	
		if(ret>=curans)curret = cur,curans = ret;
			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:112:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for(int j=0;j<vec.size()-1;j++)
      |                ~^~~~~~~~~~~~~

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