Submission #1402915
Source Code Expand
#include <bits/stdc++.h> using namespace std; double get_time() { unsigned long long a, d; __asm__ volatile("rdtsc" : "=a"(a), "=d"(d)); return (d << 32 | a) / 2500000.0; } unsigned get_random() { static unsigned y = 2463534242; return y ^= (y ^= (y ^= y << 13) >> 17) << 5; } const int n = 30; int solve(int a[n][n]) { int res = 0; while (true) { int v0, v1, v2 = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (v2 < a[i][j]) { v2 = a[i][j]; v0 = i; v1 = j; } } } if (v2 == 0) break; vector<tuple<int, int>> queue; queue.push_back(make_tuple(v0, v1)); int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; while (true) { int x = get<0>(queue.back()); int y = get<1>(queue.back()); int nx, ny, v = 0; for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx < 0 || n <= tx) continue; if (ty < 0 || n <= ty) continue; if (a[x][y] > a[tx][ty] && a[tx][ty] > v) { v = a[tx][ty]; nx = tx; ny = ty; } } if (v == 0) break; queue.push_back(make_tuple(nx, ny)); } int fx = get<0>(queue.front()); int fy = get<1>(queue.front()); int s = queue.size(); while (a[fx][fy] > 0) { for (int i = 0; i < 4; ++i) { int tx = fx + dx[i]; int ty = fy + dy[i]; if (tx < 0 || n <= tx) continue; if (ty < 0 || n <= ty) continue; if (a[fx][fy] < a[tx][ty]) goto remove; } ++res; --a[fx][fy]; printf("%d %d\n", fx + 1, fy + 1); for (int i = 1; i < s; ++i) { int px = get<0>(queue[i - 1]); int py = get<1>(queue[i - 1]); int x = get<0>(queue[i]); int y = get<1>(queue[i]); if (a[x][y] == 0 || a[px][py] > a[x][y]) break; --a[x][y]; printf("%d %d\n", x + 1, y + 1); } } remove:; } return res; } int main() { if (true) { int a[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> a[i][j]; } } solve(a); } else { for (int t = 0; t < 10; ++t) { int a[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { a[i][j] = get_random() % 100 + 1; } } int res = solve(a); cerr << res << endl; } } }
Submission Info
Submission Time | |
---|---|
Task | A - 高橋君の山崩しゲーム |
User | hoshi524 |
Language | C++14 (GCC 5.4.1) |
Score | 863967 |
Code Size | 2537 Byte |
Status | AC |
Exec Time | 10 ms |
Memory | 512 KB |
Judge Result
Set Name | test_01 | test_02 | test_03 | test_04 | test_05 | test_06 | test_07 | test_08 | test_09 | test_10 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 86553 / 100000 | 86301 / 100000 | 86509 / 100000 | 86018 / 100000 | 86355 / 100000 | 85924 / 100000 | 86854 / 100000 | 86281 / 100000 | 86575 / 100000 | 86597 / 100000 | ||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
test_01 | subtask_01_01.txt |
test_02 | subtask_01_02.txt |
test_03 | subtask_01_03.txt |
test_04 | subtask_01_04.txt |
test_05 | subtask_01_05.txt |
test_06 | subtask_01_06.txt |
test_07 | subtask_01_07.txt |
test_08 | subtask_01_08.txt |
test_09 | subtask_01_09.txt |
test_10 | subtask_01_10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 9 ms | 512 KB |
subtask_01_02.txt | AC | 10 ms | 512 KB |
subtask_01_03.txt | AC | 9 ms | 512 KB |
subtask_01_04.txt | AC | 10 ms | 512 KB |
subtask_01_05.txt | AC | 9 ms | 512 KB |
subtask_01_06.txt | AC | 9 ms | 512 KB |
subtask_01_07.txt | AC | 9 ms | 512 KB |
subtask_01_08.txt | AC | 9 ms | 512 KB |
subtask_01_09.txt | AC | 10 ms | 512 KB |
subtask_01_10.txt | AC | 10 ms | 512 KB |