Appearance
Two-step 유형 문제
Two-step 유형 문제는 풀이가 서로 단절된 두 번의 실행으로 나뉘고, 앞 단계가 만든 중간 데이터만 뒤 단계로 전달되는 형태입니다.
문제 해결 방식
Two-step 유형도 함수 구현 방식의 한 갈래입니다. 차이는 프로그램이 두 번 실행된다는 점입니다. 첫 번째 실행은 중간 데이터를 만들고, 두 번째 실행은 그 중간 데이터만 받아 질문에 답합니다.
- 앞 단계: 문제에서 준 원본 데이터를 보고 중간 데이터를 만듭니다.
- 뒤 단계: 앞 단계가 만든 중간 데이터만 보고 답합니다.
중요한 점은 두 단계가 메모리를 공유하지 않는다는 점입니다. 앞 단계에서 전역 변수나 정적 변수에 저장한 값은 뒤 단계에서 사용할 수 없습니다. 뒤 단계가 볼 수 있는 것은 앞 단계가 반환한 중간 데이터뿐입니다.
sticker 예시에서는 sticker.cpp 한 파일 안에 두 단계 함수를 함께 둡니다.
실제 문제의 인터페이스는 문제마다 다를 수 있습니다. 함수 이름과 인자, 중간 데이터의 의미가 달라져도 "앞 단계가 만든 정보만 뒤 단계로 넘어간다"는 구조는 같습니다.
입문 예시: 스티커 기록과 읽기
아래 예시는 구조를 설명하기 위한 문제입니다.
- 앞 단계 함수
make_sticker는 정수x를 보고 10행 10열 스티커를 만듭니다. - 채점기는 스티커를 회전하거나 뒤집고, 필요한 경우
0과1을 모두 바꿉니다. - 뒤 단계 함수
read_sticker는 이렇게 스캔된 스티커만 보고 원래 정수x를 반환해야 합니다.
중요한 점은 make_sticker가 실행될 때 나중에 어떤 변환이 적용될지 모른다는 점입니다. read_sticker가 실행될 때는 원래 정수 x도, 적용된 변환도 직접 주어지지 않습니다.
따라서 make_sticker가 남길 수 있는 정보는 반환한 스티커 안의 0과 1뿐입니다. 전역 변수, 파일, 표준 입출력으로 정보를 넘기는 방식은 실제 채점에서 사용할 수 없습니다.
IOI 환경과 제공 파일
로컬 테스트용 압축 자료에는 보통 다음 파일들이 들어 있습니다.
1. 헤더 파일 (sticker.h)
학생 코드와 채점기가 같은 함수 시그니처를 공유하도록 선언을 모아 둔 파일입니다.
cpp
#ifndef STICKER_H
#define STICKER_H
#include <string>
#include <vector>
std::vector<std::string> make_sticker(long long x);
long long read_sticker(std::vector<std::string> s);
#endif2. 학생이 작성하는 파일 (sticker.cpp)
이 파일 안에 앞 단계 함수와 뒤 단계 함수가 함께 들어 있습니다.
cpp
#include "sticker.h"
std::vector<std::string> make_sticker(long long x) {
// This code only shows one way to build a sticker manually.
// You may rewrite this function body freely in your submission.
std::vector<std::string> s(10, std::string(10, '0'));
if (x % 2 == 1) {
s[3][5] = '1';
}
if (x % 3 == 0) {
s[7][2] = '1';
}
return s;
}
long long read_sticker(std::vector<std::string> s) {
long long x = 0;
if (s[3][5] == '1') {
x += 1;
}
if (s[7][2] == '1') {
x += 2;
}
return x;
}sticker.cpp는 함수 형식과 데이터 흐름을 보여 주는 스켈레톤입니다. 실제 제출 전에는 두 함수의 내부를 문제에 맞게 직접 작성해야 합니다.
3. 채점기 (grader.cpp)
main이 들어 있는 파일입니다. 로컬에서 예제를 시험할 수 있도록 입력을 읽고 두 함수를 차례로 호출합니다.
cpp
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "sticker.h"
struct PhaseCase {
int index;
int ok;
std::vector<std::string> sticker;
};
static unsigned int next_random(unsigned int& state) {
state = state * 1103515245u + 12345u;
return state;
}
static std::vector<int> shuffled_order(int n) {
std::vector<int> order(n);
for (int i = 0; i < n; i++) {
order[i] = i;
}
unsigned int state = 20260705u;
for (int i = n - 1; i > 0; i--) {
int j = (int)(next_random(state) % (unsigned int)(i + 1));
std::swap(order[i], order[j]);
}
return order;
}
static std::pair<int, int> rotate_cell(int r, int c, int k) {
const int n = 10;
for (int i = 0; i < k; i++) {
int nr = c;
int nc = n - 1 - r;
r = nr;
c = nc;
}
return std::make_pair(r, c);
}
static std::vector<std::string> transform_sticker(std::vector<std::string> s, int transform, int invert) {
const int n = 10;
std::vector<std::string> result(n, std::string(n, '0'));
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int sr = r;
int sc = c;
if (transform >= 4) {
sc = n - 1 - sc;
}
std::pair<int, int> moved = rotate_cell(sr, sc, transform % 4);
char value = s[r][c];
if (invert) value = (value == '0' ? '1' : '0');
result[moved.first][moved.second] = value;
}
}
return result;
}
static bool valid_sticker(const std::vector<std::string>& s) {
if ((int)s.size() != 10) return false;
for (const std::string& row : s) {
if ((int)row.size() != 10) return false;
for (char ch : row) {
if (ch != '0' && ch != '1') return false;
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin >> T;
std::vector<PhaseCase> cases(T);
for (int tc = 0; tc < T; tc++) {
long long x;
int transform, invert;
std::cin >> x >> transform >> invert;
std::vector<std::string> s = make_sticker(x);
int ok = valid_sticker(s) && 0 <= transform && transform < 8 && (invert == 0 || invert == 1);
std::vector<std::string> scanned(10, std::string(10, '0'));
if (ok) {
scanned = transform_sticker(s, transform, invert);
}
cases[tc].index = tc;
cases[tc].ok = ok;
cases[tc].sticker = scanned;
}
std::vector<long long> answers(T, -1);
for (int idx : shuffled_order(T)) {
const PhaseCase& cur = cases[idx];
if (cur.ok) {
answers[cur.index] = read_sticker(cur.sticker);
}
}
for (long long answer : answers) {
if (answer == -1) {
std::cout << "invalid\n";
} else {
std::cout << answer << '\n';
}
}
return 0;
}로컬 샘플 그레이더의 한계
실제 채점에서는 두 단계가 서로 다른 실행으로 분리될 수 있습니다. 반면 로컬 샘플 그레이더는 편의를 위해 한 프로그램 안에서 두 함수를 차례로 호출하는 경우가 많습니다.
- 로컬에서 전역 변수나
static변수에 의존한 코드가 우연히 동작할 수 있습니다. - 실제 채점에서는 그런 코드가 실패할 수 있습니다.
- 뒤 단계 함수가 사용할 수 있는 정보는 문제에서 인자로 전달된 값과 앞 단계가 만든 중간 데이터뿐이라고 생각해야 합니다.
4. 예제 입출력 파일 (examples/01.in.txt, examples/01.out.txt)
로컬에서 채점기를 돌려 볼 수 있도록 예제 입력과 기대 출력이 함께 들어 있습니다. 입력은 경우의 수 T와, 각 경우의 정수 x, 변환 번호, 색 반전 여부 순서입니다.
examples/01.in.txt:
text
1
42 1 0examples/01.out.txt:
text
42이 예제에서 채점기는 make_sticker(42)를 호출한 뒤 변환 번호 1을 적용합니다. read_sticker는 변환된 스티커만 보고 42를 반환해야 합니다.
중간 메시지와 채점
서버는 여러 테스트 케이스에 대해 두 단계를 차례로 실행합니다. 뒤 단계가 질문에 올바르게 답해야 해당 테스트를 통과합니다.
여러 테스트를 묶어 서브태스크(Subtask)를 구성하는 방식은 Batch 문제와 같습니다. 차이는 중간 데이터의 길이 또는 값 범위에 제한이 붙을 수 있다는 점입니다. sticker 예시에서는 반환할 수 있는 중간 데이터가 10행 10열 스티커로 제한됩니다.
컴파일 및 실행 방법
로컬에서는 학생 파일과 채점기 파일을 함께 컴파일합니다. main은 grader.cpp 안에 있습니다.
Windows/WSL:
bash
g++ grader.cpp sticker.cpp -std=gnu++20 -O2 -pipe -Wall -o mainmacOS:
bash
g++-13 grader.cpp sticker.cpp -std=gnu++20 -O2 -pipe -Wall -o main컴파일이 끝나면 실행 파일(main)이 생성됩니다. 예제 입력을 리다이렉션해 실행하면 두 단계가 순서대로 호출됩니다.
bash
./main < ../examples/01.in.txt출력값은 ../examples/01.out.txt와 비교합니다. 스켈레톤 상태에서는 예제 출력이 맞지 않을 수 있습니다.
로컬 테스트에는 grader.cpp를 사용합니다. 제출할 때는 sticker.cpp만 제출합니다. sticker.h와 grader.cpp는 제출 파일이 아닙니다.