Submission #1018218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018218		NintsiChkhaidze	Jousting tournament (IOI12_tournament)	C++17	49 / 100	563 ms	3152 KiB

tournament

#include <bits/stdc++.h>
#define pb push_back
#define pii pair <int,int>
#define f first
#define s second
#define left h*2,l,(l+r)/2
#define right h*2+1,(l+r)/2+1,r
using namespace std;
const int M = 10000+5;

vector <int> g[M];
int dp[M],par[M];

void dfs(int x,int par){
	for (int to: g[x]){
		dfs(to,x);
		dp[x]=max(dp[x],dp[to]);
	}
}

int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){
	int n = N;
	int id = 1;
	
	vector <int> leaves;
	leaves.pb(id);
	
	for (int i = C - 1; i >= 0; i--){
		int l = S[i],r = E[i],cnt = 0;
		
		vector <int> nw;
		for (int j=0;j<l;j++){
			nw.pb(leaves[j]);
		}
		
		for (int j = l; j <= r; j++){
			nw.pb(++id);
			par[id] = leaves[l];
			g[leaves[l]].pb(id);
		}
			
		for (int j = l + 1; j < leaves.size(); j++)
			nw.pb(leaves[j]);
			
		leaves = nw;
	}
	
	int ans=-1,pos=-1;
	for (int i=0;i<n;i++){
		vector <int> v;
		int l = 0;
		for (int j = 0; j < N; j++){
			if (i == j) v.pb(R);
			else v.pb(K[l++]);
		}
		
		for (int j = 1; j <= id; j++)
			dp[j] = 0;
			
		int x = 0;
		for (int j = 0; j < n; j++){
			dp[leaves[j]] = v[j];
			if (v[j] == R){
				x = leaves[j];	
			}
		}
		
		dfs(1,1);
		int cur = 0;
		x = par[x];
		while (x && dp[x] == R){
			++cur;
			x = par[x];
		}
		
		if (cur > ans){
			ans = cur;
			pos = i;
		}
	}
	
	return pos;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int j = l + 1; j < leaves.size(); j++)
      |                       ~~^~~~~~~~~~~~~~~
tournament.cpp:29:25: warning: unused variable 'cnt' [-Wunused-variable]
   29 |   int l = S[i],r = E[i],cnt = 0;
      |                         ^~~

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