oj.uz

Submission #913003

# Submission time Handle Problem Language Result Execution time Memory
913003 2024-01-20T05:16:12 Z Faisal_Saqib Jousting tournament (IOI12_tournament) C++17
17 / 100
 1000 ms 6456 KB 
#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[n],ce[n];
	{
		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);
	for(int p=0;p<(n-1);p++)
	{
		int a[n],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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 21 ms 344 KB Output is correct
4 Correct 26 ms 348 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 20 ms 348 KB Output is correct
7 Correct 21 ms 492 KB Output is correct
8 Correct 23 ms 480 KB Output is correct
9 Correct 8 ms 348 KB Output is correct
10 Correct 10 ms 604 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 524 KB Output is correct
2 Execution timed out 1028 ms 856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1028 ms 6456 KB Time limit exceeded
2 Halted 0 ms 0 KB -