이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#include "doll.h"
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = (int)5e5 + 10;
int lst = 0;
vector<int>trans[N];
int m;
int x[N],y[N];
int build(vector<int>k, int ROOT){
if(sz(k) == 1){
if(k[0] == -1){
x[lst]=lst;
y[lst]=ROOT;
lst++;
return lst-1;
}
return k[0];
}
// assert(sz(k) != 0);
vector<int>st[2];
for(int i = 0; i < sz(k); ++i)
st[i&1].pb(k[i]);
int v = lst++;
if(ROOT==-1){
ROOT = v;
}
int A=build(st[0],ROOT),B=build(st[1],ROOT);
x[v]=A;
y[v]=B;
return v;
}
int code(int f){
if(f <= m)
return f;
return -(f-m);
}
bool good(int f){
int pw=1;
int F = f;
while(f){
f>>=1;
pw<<=1;
}
pw>>=1;
if(pw==F)
return true;
return false;
}
void create_circuit(int M, std::vector<int> A){
m = M;
A.push_back(0);
A.insert(A.begin(), 0);
for(int i = 0; i < sz(A) - 1; ++i){
trans[A[i]].push_back(A[i + 1]);
}
lst = M + 1;
vector < int > C(M + 1);
for(int i = 0; i <= M; ++i){
if(sz(trans[i]) == 0)
continue;
reverse(all(trans[i]));
while(!good(sz(trans[i]))){
trans[i].pb(-1);
}
reverse(all(trans[i]));
// cout << " SZ " << sz(trans[i]) << endl;
if(sz(trans[i]) == 1){
C[i] = trans[i][0];
}else{
C[i] = code(build(trans[i], -1));
}
}
vector<int>X(lst-1-M),Y(lst-1-M);
for(int f=0;f<sz(X);++f){
X[f]=code(x[M+1+f]);
Y[f]=code(y[M+1+f]);
}
// cout << "LOL \n";
// for(int i = 0; i <= M; ++i)
// cout << C[i] << '\n';
// for(int f = 0; f < sz(X); ++f){
// cout << X[f] << ' ' << Y[f] << endl;
// }
// cout << endl;
answer(C,X,Y);
}
/*
4 6
1 2 1 3 1 4
*/
# | 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... |