Submission #913005

#	Time	Username	Problem	Language	Result	Execution time	Memory
913005		Faisal_Saqib	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1045 ms	6304 KiB

tournament

#pragma once
#include <iostream>
using namespace std;
struct SegmentTree
{
	int mx=-1;
	int s,e;
	SegmentTree* next[2];
	SegmentTree(int l,int r)
	{
		s=l;
		e=r;
		if(s!=e)
		{
			int mid=(s+e)/2;
			next[0]=new SegmentTree(s,mid);
			next[1]=new SegmentTree(mid+1,e);
		}
	}
	void Update(int& i,int& x)
	{
		if(i<s or e<i)
			return ;
		if(s==e)
		{
			mx=x;
			return;
		}
		next[0]->Update(i,x);
		next[1]->Update(i,x);
		mx=max(next[0]->mx,next[1]->mx);
	}
	int get(int& l,int& r)
	{
		if(r<s or e<l)
			return -1;
		if(l<=s and e<=r)
		{
			return mx;
		}
		return max(next[0]->get(l,r),next[1]->get(l,r));
	}
};
//for an i : Who is representing this index and whom is this index representing
int GetBestPosition(int n, int c, int r, int k[], int s[], int e[])
{
	// Lets change the queries from the changed array to the original array
	int cs[c],ce[c];
	{
		int a[n],mi[n],mx[n];
		for(int i=0;i<n;i++)
			a[i]=mi[i]=mx[i]=i;
		int len=n;
		for(int ro=0;ro<c;ro++)
		{
			int ns=a[s[ro]];
			int ne=a[e[ro]];
			for(int l=s[ro];l<=e[ro];l++)
			{
				ns=min(ns,mi[a[l]]);
				ne=max(ne,mx[a[l]]);
			}
			for(int l=s[ro];l<=e[ro];l++)
			{
				mi[a[l]]=min(ns,mi[a[l]]);
				mx[a[l]]=max(ne,mx[a[l]]);
			}
			for(int j=e[ro];j<len;j++)
				a[j+s[ro]-e[ro]]=a[j];
			len=len-e[ro]+s[ro];
			cs[ro]=ns;
			ce[ro]=ne;
		}
	}
	int wins=0;
	int poss=0;
	SegmentTree* st=new SegmentTree(0,n-1);
  int a[n];
	for(int p=0;p<(n-1);p++)
	{
		int win=0;
		for(int j=0;j<p;j++)
			a[j]=k[j];
		a[p]=r;
		for(int j=p;j<(n-1);j++)
			a[j+1]=k[j];
		for(int lk=0;lk<n;lk++)
			st->Update(lk,a[lk]);
		for(int round=0;round<c;round++)
		{
			int mx=st->get(cs[round],ce[round]);
			if(mx==r)
				win++;
		}
		if(wins<win)
		{
			wins=win;
			poss=p;
		}
	}
	return poss;
}

Compilation message (stderr)

tournament.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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