이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |