oj.uz

Submission #100250

# Submission time Handle Problem Language Result Execution time Memory
100250 2019-03-10T05:46:09 Z StevenH Mechanical Doll (IOI18_doll) C++14
100 / 100
 165 ms 12376 KB 
#include "doll.h"
//#include <vector>
#include <iostream>
using namespace std;
int status[400005];	// 0 X  1 Y 
vector<int> XX;
vector<int> YY;
int ansx[400005],ansy[400005];
int p = 1;
int pk = 0;
int ff(int tt,int sp)
{
  //cout<<sp<<endl;
  if(ansx [tt] >0 && status[tt]==0) pk =1;
  if(pk==1)return -1;
  if(status[tt]==0)
  {
  	status[tt]=1;
  	if(XX[tt] == 0)
  	{
  	  ansx[tt]=p;
  	  //cout<<tt<<" x "<<p<<endl;
  	  p++;
  	  return 0;
	}
	else
	{	
  	  //cout<<tt<<" "<<XX[tt]<<" "<<-1*XX[tt]-1<<endl;
  	  ff(-1*XX[tt]-1,sp);
    }
  }
  else
  {
  	status[tt]=0;
  	if(YY[tt] == 0 && sp != tt)
  	{
  	  //cout<<tt<<" y "<<p<<endl;
  	  ansy[tt]=p;
	  p++;
	  return 0;	
	} 
  	else if(sp != tt)
  	{ 
  	  //cout<<tt<<" "<<YY[tt]<<" "<<-1*YY[tt]-1<<endl;
  	  ff(-1*YY[tt]-1,sp);
    } 
  }   
  
  return 0;
}
int f(vector<int> X, vector<int> Y,int sp)
{
  int i;
  XX=X;
  YY=Y;
  while(true)
  {
  	i=ff(0,sp);
  	//cout<<i<<" "<<endl;
  	if(i == -1)return 0;// 從第0位  S=-1 開始   	
  }
  return 0;
}
void create_circuit(int M, vector<int> A) 
{
  vector<int> C(M+1);
  vector<int> X(400005),Y(400005);
  int two[20];
  int i, j, k = 1, t, tt;
  int N = A.size();
  for(i=0; i<=M; i++)C[i]=-1;  //起點和觸發器連接到root結點 
  int temp = N;
  k=0;
  while(temp>0)	//N轉換成二進制 
  {
  	k++;
  	two[k]=temp%2; 
  	temp/=2;
  }
  for(i=1;i<k;i++)Y[i]=-1*(i+1); // 形成鏈 鏈長為 N 的二進制長度 
 
  Y[k]=0; // 鏈尾指起點  
  t = k+1; // 開關序號 
  for(j=k;j>0;j--)
  {
  	if(two[j]==1 && j!=1) // 建樹 樹深為 k-1 
  	{
  	  tt=1;
	  X[k-j+1]=-1*t;
  	  for(i=0;i<j-1;i++)tt*=2;
  	  // tt 為樹的結點數 
  	  //cout<<t<<" "<<tt<<endl;
  	  for(i=t;i<t+tt/2-1;i++)
  	  {
  	    X[i] = -1*((i-t)*2+1+t);
		Y[i] = -1*((i-t)*2+2+t); 
	  }
	  t=t+tt-1;
	}
	else if(two[j]==0)X[k-j+1]=-1;
  }
  
  for(i=0;i<t-1;i++)
  {
    X[i]=X[i+1];
    Y[i]=Y[i+1];
  }
  t--;
  X.resize(t);
  Y.resize(t);
  for(i=0;i<t;i++)
  {
  	status[i]=0;
  	//cout<<i<<" "<<(i+1)*-1<<" "<<X[i]<<" "<<Y[i]<<endl; 
  }
  
  f(X,Y,k-1);
  
  for(i=0;i<t;i++)
  {
  	if(ansx[i] != 0)X[i] = ansx[i];
  	if(ansy[i] != 0)Y[i] = ansy[i];
  }
  //for(i=0;i<t;i++)cout<<i<<" "<<(i+1)*-1<<" "<<X[i]<<" "<<Y[i]<<endl; 
  //for(i=0;i<N;i++)cout<<A[i]<<" ";
  //cout<<endl;
  for(i=0;i<t;i++)
  {
  	if(X[i]>0)X[i]=A[X[i]-1];
  	if(Y[i]>0)Y[i]=A[Y[i]-1];
  }
  //cout<<X.size()<<" "<<Y.size()<<endl;
  //for(i=0;i<=M;i++)cout<<C[i]<<endl;
  //for(i=0;i<t;i++)cout<<i<<" "<<(i+1)*-1<<" "<<X[i]<<" "<<Y[i]<<endl; 
  /*int S=X.size();
  for (int i = 0; i <= M; ++i) {
    if (!(-S <= C[i] && C[i] <= M)) {
      cout<<"wrong serial number";
    }
  }
  for (int j = 1; j <= S; ++j) {
    if (!(-S <= X[j - 1] && X[j - 1] <= M)) {
      cout<<"wrong serial number";
    }
    if (!(-S <= Y[j - 1] && Y[j - 1] <= M)) {
      cout<<"wrong serial number";
    }
  }*/
  answer(C, X, Y);
}
/*
int main()
{
	int N = 9;
	int i;
	int a[N] = {1,2,3,4,3,2,1,2,1}; 
	vector<int> A;
	A.resize(N);
	for(i=0;i<N;i++)A[i]=a[i];
	create_circuit(4,A);
	//system("pause");
	return 0;
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 7084 KB Output is correct
3 Correct 48 ms 6688 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 77 ms 8428 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 7084 KB Output is correct
3 Correct 48 ms 6688 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 77 ms 8428 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 102 ms 9352 KB Output is correct
9 Correct 95 ms 9660 KB Output is correct
10 Correct 165 ms 12376 KB Output is correct
11 Correct 3 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 57 ms 7084 KB Output is correct
3 Correct 48 ms 6688 KB Output is correct
4 Correct 4 ms 3404 KB Output is correct
5 Correct 13 ms 4556 KB Output is correct
6 Correct 77 ms 8428 KB Output is correct
7 Correct 3 ms 3404 KB Output is correct
8 Correct 102 ms 9352 KB Output is correct
9 Correct 95 ms 9660 KB Output is correct
10 Correct 165 ms 12376 KB Output is correct
11 Correct 3 ms 3404 KB Output is correct
12 Correct 3 ms 3404 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct
14 Correct 143 ms 12016 KB Output is correct
15 Correct 90 ms 8968 KB Output is correct
16 Correct 146 ms 11804 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 4 ms 3404 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 161 ms 12172 KB Output is correct
21 Correct 3 ms 3456 KB Output is correct
22 Correct 3 ms 3404 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 104 ms 8584 KB Output is correct
3 Correct 87 ms 8588 KB Output is correct
4 Correct 134 ms 11240 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Correct 104 ms 8584 KB Output is correct
3 Correct 87 ms 8588 KB Output is correct
4 Correct 134 ms 11240 KB Output is correct
5 Correct 139 ms 11656 KB Output is correct
6 Correct 134 ms 11452 KB Output is correct
7 Correct 136 ms 11560 KB Output is correct
8 Correct 141 ms 11424 KB Output is correct
9 Correct 115 ms 8636 KB Output is correct
10 Correct 139 ms 11300 KB Output is correct
11 Correct 125 ms 11244 KB Output is correct
12 Correct 87 ms 8492 KB Output is correct
13 Correct 92 ms 8636 KB Output is correct
14 Correct 93 ms 8792 KB Output is correct
15 Correct 98 ms 8816 KB Output is correct
16 Correct 5 ms 3532 KB Output is correct
17 Correct 81 ms 8636 KB Output is correct
18 Correct 83 ms 8508 KB Output is correct
19 Correct 96 ms 8544 KB Output is correct
20 Correct 147 ms 11296 KB Output is correct
21 Correct 151 ms 11236 KB Output is correct
22 Correct 139 ms 11300 KB Output is correct