이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
const int MN = 2e5;
int S;
std::vector<int> X, Y;
bool root[MN], state[MN];
int dfs(int l, int r, int ql)
{
int n=++S; X.push_back(1), Y.push_back(1);
if(r-l>2)
{
int m=l+(r-l)/2;
if(ql < m) X[n-1] = dfs(l, m, ql);
Y[n-1] = dfs(m, r, ql);
}
else
root[n]=1;
return n;
}
void create_circuit(int M, std::vector<int> A) {
X.reserve(MN);
Y.reserve(MN);
int N = A.size();
std::vector<int> C(M + 1);
C[0]=A[0];
if(N==1)
{
C[C[0]]=0;
answer(C, X, Y);
return;
}
for(int i=1;i<=M;++i)
C[i]=-1;
//for(auto x:A) printf("%d ", x); printf("\n");
std::rotate(A.begin(), A.begin()+1, A.end());
A.back()=0;
if(A.size()&1)
A.insert(A.begin(), -1);
//for(auto x:A) printf("%d ", x); printf("\n");
int d = 31 - __builtin_clz((int)A.size()-1);
assert((1<<d+1) >= A.size() && A.size() > (1<<d));
int top;
top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
for(int& x:X) x*=-1;
for(int& x:Y) x*=-1;
int ctr=0;
int n=-top;
for(;n != 0;)
{
//printf("ideal: %d\n", n);
if(n > 0)
n = -top;
else if(root[-n])
{
state[-n] ^= 1;
assert(ctr < A.size());
n = (state[-n] ? X[-n-1] : Y[-n-1]) = A[ctr++];
}
else
{
state[-n] ^= 1;
n = state[-n] ? X[-n-1] : Y[-n-1];
}
}
//printf("%d %lu\n", ctr, A.size());
assert(ctr == A.size());
answer(C, X, Y);
}
컴파일 시 표준 에러 (stderr) 메시지
In file included from /usr/include/c++/10/cassert:44,
from doll.cpp:3:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:52:14: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
52 | assert((1<<d+1) >= A.size() && A.size() > (1<<d));
| ~^~
doll.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | assert((1<<d+1) >= A.size() && A.size() > (1<<d));
| ~~~~~~~~~^~~~~~~~~~~
doll.cpp:52:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
52 | assert((1<<d+1) >= A.size() && A.size() > (1<<d));
| ~~~~~~~~~^~~~~~~~
doll.cpp:55:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
55 | top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
| ~^~
doll.cpp:55:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
55 | top = dfs(0, 1<<d+1, (1<<d+1)-A.size());
| ~^~
In file included from /usr/include/c++/10/cassert:44,
from doll.cpp:3:
doll.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | assert(ctr < A.size());
| ~~~~^~~~~~~~~~
doll.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | assert(ctr == A.size());
| ~~~~^~~~~~~~~~~
# | 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... |