| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 38 | 30 | 25 | 75.758% |
$3$차원 공간에 세 개의 점 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$가 있다.
어떤 점 $\left( x,y,z \right)$에 대해 다음 연산들을 적용할 수 있다.
X) : $\left( x,y,z \right)\mapsto\left( x,-z,y \right)$Y) : $\left( x,y,z \right)\mapsto\left( z,y,-x \right)$Z) : $\left( x,y,z \right)\mapsto\left( -y,x,z \right)$XX) : $\left( x,y,z \right)\mapsto\left( x,-y,-z \right)$YY) : $\left( x,y,z \right)\mapsto\left( -x,y,-z \right)$ZZ) : $\left( x,y,z \right)\mapsto\left( -x,-y,z \right)$XY 혹은 YX) : $\left( x,y,z \right)\mapsto\left( x,y,-z \right)$YZ 혹은 ZY) : $\left( x,y,z \right)\mapsto\left( -x,y,z \right)$ZX 혹은 XZ) : $\left( x,y,z \right)\mapsto\left( x,-y,z \right)$서현이는 $1$번부터 $N$번까지 $N$개의 연산을 가지고 있다.
다음과 같은 쿼리 $Q$개를 독립적으로 처리해 보자. 즉, 모든 쿼리에 대해 세 점의 초기 위치는 각각 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에서 시작한다.
첫 번째 줄에 연산의 개수 $N(1\le N\le 100\, 000)$이 주어진다.
두 번째 줄에 $N$개의 연산 $O_1,O_2,\cdots ,O_N$이 공백으로 구분되어 주어진다. $O_i$는 X, Y, Z, XX, YY, ZZ, XY, YX, YZ, ZY, ZX, XZ 중 하나이다.
세 번째 줄에 쿼리의 개수 $Q(1\le Q\le 100\, 000)$가 주어진다.
네 번째 줄부터 $Q$줄에 걸쳐 $i$번째 쿼리를 의미하는 정수 $l_i,r_i(1\le l_i\le r_i\le N)$가 공백으로 구분되어 주어진다.
첫 번째 줄부터 $3\times Q$줄에 걸쳐 각 쿼리에 대한 답을 다음과 같이 출력한다.
4 X Y XY Z 3 1 2 2 4 3 4
0 0 -1 1 0 0 0 -1 0 0 0 1 -1 0 0 0 1 0 0 1 0 -1 0 0 0 0 -1
첫 번째 쿼리는 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에 X를 적용하면 $\left( 1,0,0 \right)$, $\left( 0,0,1 \right)$, $\left( 0,-1,0 \right)$가 된다. 여기에 Y를 적용하면 $\left( 0,0,-1 \right)$, $\left( 1,0,0 \right)$, $\left( 0,-1,0 \right)$가 된다.
두 번째 쿼리는 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에 Y를 적용하면 $\left( 0,0,-1 \right)$, $\left( 0,1,0 \right)$, $\left( 1,0,0 \right)$가 된다. 여기에 XY를 적용하면 $\left( 0,0,1 \right)$, $\left( 0,1,0 \right)$, $\left( 1,0,0 \right)$가 된다. 여기에 Z를 적용하면 $\left( 0,0,1 \right)$, $\left( -1,0,0 \right)$, $\left( 0,1,0 \right)$가 된다.
세 번째 쿼리는 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에 XY를 적용하면 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,-1 \right)$가 된다. 여기에 Z를 적용하면 $\left( 0,1,0 \right)$, $\left( -1,0,0 \right)$, $\left( 0,0,-1 \right)$가 된다.
5 XY YX Z Z ZZ 3 1 2 2 3 3 5
1 0 0 0 1 0 0 0 1 0 1 0 -1 0 0 0 0 -1 1 0 0 0 1 0 0 0 1
첫 번째 쿼리는 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에 XY를 적용하면 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,-1 \right)$가 된다. 여기에 YX를 적용하면 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$가 된다.
두 번째 쿼리는 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,1 \right)$에 YX를 적용하면 $\left( 1,0,0 \right)$, $\left( 0,1,0 \right)$, $\left( 0,0,-1 \right)$가 된다. 여기에 Z를 적용하면 $\left( 0,1,0 \right)$, $\left( -1,0,0 \right)$, $\left( 0,0,-1 \right)$가 된다.
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 G번