oj.uz

Submission #75033

# Submission time Handle Problem Language Result Execution time Memory
75033 2018-09-08T05:10:56 Z charlies_moo Turnir (COCI17_turnir) C++
100 / 100
 730 ms 28076 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int n,anss;
int ans[2000000];

struct Node
{
	int num,idx;
}a[2000000];

bool cmp(Node a,Node b)
{
	return a.num<b.num;
}

int pow2(int a)
{
	int ret=1;
	for(int i=1;i<=a;i++)
		ret*=2;
	return ret;
}

int log2(int from)
{
	int i;
	for(i=0;pow2(i)<=from;i++);
	return i-1;
}

int main()
{
	cin>>n;
	int deep=n,from_;
	n=pow2(n);
	for(int i=1;i<=n;i++)
	{
		a[i].idx=i;
		cin>>a[i].num;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int k=a[i].num;
		from_=i;
		while(a[i].num<=k && i<=n)
			i++;
		i--,anss=deep-log2(i);
		for(int j=from_;j<=i;j++)
			ans[a[j].idx]=anss;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 5 ms 472 KB Output is correct
5 Correct 28 ms 1000 KB Output is correct
6 Correct 48 ms 1908 KB Output is correct
7 Correct 92 ms 3540 KB Output is correct
8 Correct 138 ms 6952 KB Output is correct
9 Correct 368 ms 13880 KB Output is correct
10 Correct 730 ms 28076 KB Output is correct