제출 #100250

#제출 시각아이디문제언어결과실행 시간메모리
100250StevenH자동 인형 (IOI18_doll)C++14
100 / 100
165 ms12376 KiB
#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; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...