oj.uz

Submission #282943

# Submission time Handle Problem Language Result Execution time Memory
282943 2020-08-25T07:38:08 Z tinjyu Mechanical Doll (IOI18_doll) C++14
100 / 100
 142 ms 13124 KB 
#include <iostream>
#include <vector>
#include "doll.h"
using namespace std;
int l[1000005],r[1000005],num[25],d[1000005],b[1000005],x1[1000005],x2[1000005],X[1000005],p=0,Y[1000005];
int qs(int s,int e){
	int l=s,r=e,mid=(d[l]+d[r])/2;
	while(l<=r)
	{
		while(d[l]<mid)l++;
		while(d[r]>mid)r--;
		if(l<=r)
		{
			swap(d[l],d[r]);
			swap(b[l],b[r]);
			l++;
			r--;
		}
	}
	if(s<r)qs(s,r);
	if(l<e)qs(l,e);
	return 0;
}
int find(int x){
	if(x==0)return 0;
	if(x<0)return 1;
	if(find(l[x])==0 && find(r[x])==0)
	{
		return 0;
	}
	else if(find(l[x])==0 && find(r[x])==1)
	{
		l[x]=0;
	}
	return 1;
 
}
int solve(int t){
	int e=p;
	if(l[t]>=1)
	{
		p++;
		x1[e]=p;
		solve(l[t]);
	}
	else x1[e]=l[t];
	if(r[t]>=1)
	{
		p++;
		x2[e]=p;
		solve(r[t]);
	}
	else x2[e]=r[t];
	return 0;
}
void create_circuit(int M, std::vector<int> A) {
  int n = A.size(); 
  n++;
  A[n-1]=1;
  int t=1;
	while(t<n)
	{
		t*=2;
		p++;
	}
  std::vector<int> C(M + 1);
  C[0] = -1;
  for (int i = 1; i <= M; ++i) {
    C[i] = 1;
  }
  
	num[1]=-1;
	for(int i=1;i<=t+1;i++)
	{
		num[1]++;
		for(int j=1;j<=p+1;j++)
		{
			if(num[j]==2)
			{
				num[j]=0;
				num[j+1]++;
			}
			else break;
		}
		int q=1;
		for(int j=p;j>=1;j--)
		{
			d[i]+=q*num[j];
			q*=2;
		}
	}
	for(int i=t;i>=t-n+1;i--)b[i]=i-1;
	qs(t-n+1,t);
	for(int i=1;i<=t-1;i++)
	{
		l[i]=(i*2);
		r[i]=(i*2+1);
		if(i*2>t-1)l[i]=0;
		if(i*2+1>t-1)r[i]=0;
	}
	for(int i=t-n+1;i<=t;i++)
	{
		if(b[i]%2==1)r[(t+b[i])/2]=A[i-(t-n)-1]*-1;
		else l[(t+b[i])/2]=A[i-(t-n)-1]*-1;
	}
	find(1);
	p=1;
	solve(1);
	C[0]=-1;
	for(int i=0;i<=M;i++)C[i]=-1;
	std::vector<int> X(p), Y(p);
	for(int i=0;i<p;i++)
	{
		X[i]=x1[i+1]*-1;
		if(X[i]==0)X[i]=-1;
	}
	for(int i=0;i<p;i++)
	{
		Y[i]=x2[i+1]*-1;
		if(Y[i]==0)Y[i]=-1;
	}
	Y[p-1]=0;
	answer(C, X, Y);
	return ;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 45 ms 5828 KB Output is correct
3 Correct 42 ms 5452 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 63 ms 7364 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 45 ms 5828 KB Output is correct
3 Correct 42 ms 5452 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 63 ms 7364 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 76 ms 9820 KB Output is correct
9 Correct 102 ms 10164 KB Output is correct
10 Correct 126 ms 13124 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 45 ms 5828 KB Output is correct
3 Correct 42 ms 5452 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 11 ms 1484 KB Output is correct
6 Correct 63 ms 7364 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 76 ms 9820 KB Output is correct
9 Correct 102 ms 10164 KB Output is correct
10 Correct 126 ms 13124 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 113 ms 12800 KB Output is correct
15 Correct 81 ms 9396 KB Output is correct
16 Correct 112 ms 12600 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 110 ms 13004 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 74 ms 9044 KB Output is correct
3 Correct 73 ms 9028 KB Output is correct
4 Correct 110 ms 11956 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 74 ms 9044 KB Output is correct
3 Correct 73 ms 9028 KB Output is correct
4 Correct 110 ms 11956 KB Output is correct
5 Correct 126 ms 12444 KB Output is correct
6 Correct 113 ms 12236 KB Output is correct
7 Correct 107 ms 12352 KB Output is correct
8 Correct 113 ms 12100 KB Output is correct
9 Correct 72 ms 9044 KB Output is correct
10 Correct 142 ms 12100 KB Output is correct
11 Correct 134 ms 11972 KB Output is correct
12 Correct 70 ms 9028 KB Output is correct
13 Correct 78 ms 9148 KB Output is correct
14 Correct 73 ms 9244 KB Output is correct
15 Correct 76 ms 9284 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 63 ms 7492 KB Output is correct
18 Correct 71 ms 9012 KB Output is correct
19 Correct 88 ms 9028 KB Output is correct
20 Correct 116 ms 12088 KB Output is correct
21 Correct 128 ms 11968 KB Output is correct
22 Correct 103 ms 11968 KB Output is correct