oj.uz

답안 #100141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100141 2019-03-09T13:50:02 Z StevenH 자동 인형 (IOI18_doll) C++14
0 / 100
 85 ms 8492 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 開始   	
  }
  //cout<<"*";
  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>1;j--)   /******/
  {
  	if(two[j]==1) // 建樹 樹深為 k-1 
  	{
  	  tt=1;
	  X[k-j+1]=-1*t;
  	  for(i=0;i<j-1;i++)tt*=2;
  	  // tt 為樹的結點數 
  	  tt--;
  	  //cout<<t<<" "<<tt<<endl;
  	  for(i=t;i<t+tt/2;i++)
  	  {
  	    X[i] = -1*((i-t)*2+1+t);
		Y[i] = -1*((i-t)*2+2+t); 
	  }
	  t=t+tt;
	  //if(j==1)t++;
	}
	else 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<<ansx[i]<<" "<<ansy[i]<<endl;
  //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);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:139:7: warning: unused variable 'S' [-Wunused-variable]
  139 |   int S=X.size();
      |       ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 54 ms 7192 KB state 'Y'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 54 ms 7192 KB state 'Y'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3404 KB Output is correct
2 Incorrect 54 ms 7192 KB state 'Y'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3404 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Incorrect 85 ms 8492 KB state 'Y'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Incorrect 85 ms 8492 KB state 'Y'
3 Halted 0 ms 0 KB -