Submission #228730


Source Code Expand

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>

using namespace std;
typedef long long i64;
typedef vector<int> ivec;
#define MOD 1000000007

int in() { int x; scanf("%d", &x); return x; }

int H, W, N, A[200050], R[200050], S[200050];

struct del {
	int a, b;
} D[200050];

int left(int r, int c);
int right(int r, int c) {
	r %= (2 * W);
	if (c + r < W - 1) {
		return c + r + 1;
	}
	int move = (W - 2) - c;
	return left(r - move - 2, W - 2);
}
int left(int r, int c) {
	r %= (2 * W);
	if (c - r >= 0) {
		return c - r;
	}
	int move = c;
	return right(r - move - 2, 0);
}

void doit(int r, int c) {
	int L = left(r, c);
	int R = right(r, c);
	swap(A[L], A[R]);
}

int main()
{
	H = in();
	W = in();
	N = in();

	for (int i = 0; i < W; ++i) {
		A[i] = i;
	}

	for (int i = 0; i < N; ++i) {
		D[i].a = in() - 1;
		D[i].b = in() - 1;
	}

	sort(D, D + N, [](const del& a, const del& b) {
		return a.a < b.a;
	});

	for (int i = 0; i < N; ++i) {
		doit(D[i].a, D[i].b);
	}


	if (H % 2 == 0) {
		R[0] = right(H - 2, 0);
		R[W - 1] = left(H - 2, W - 2);
		for (int i = 1; i < W - 1; i += 2) {
			R[i] = right(H - 1, i);
			R[i + 1] = left(H - 1, i);
		}
	}
	else {
		for (int i = 0; i < W; i += 2) {
			R[i] = right(H - 1, i);
			R[i + 1] = left(H - 1, i);
		}
	}

	for (int i = 0; i < W; ++i) {
		S[A[R[i]]] = i + 1;
	}
	for (int i = 0; i < W; ++i) {
		printf("%d\n", S[i]);
	}

	return 0;
}

Submission Info

Submission Time
Task D - Dense Amidakuji
User Operasan
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1579 Byte
Status AC
Exec Time 177 ms
Memory 5800 KiB

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:15:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 11
Set Name Test Cases
All 000, 001, 002, 003, 004, 005, 006, 007, 008, 900, 901
Case Name Status Exec Time Memory
000 AC 22 ms 800 KiB
001 AC 111 ms 2208 KiB
002 AC 113 ms 2212 KiB
003 AC 177 ms 5796 KiB
004 AC 161 ms 5800 KiB
005 AC 157 ms 5800 KiB
006 AC 116 ms 3620 KiB
007 AC 83 ms 4568 KiB
008 AC 74 ms 1960 KiB
900 AC 19 ms 684 KiB
901 AC 21 ms 800 KiB