제출 #100250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100250		StevenH	자동 인형 (IOI18_doll)	C++14	100 / 100	165 ms	12376 KiB

doll

#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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56