QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719523 | #7325. Tube Master II | hos.lyric🐇 | AC ✓ | 2ms | 4292kb | C++14 | 3.6kb | 2024-11-07 02:53:55 | 2024-11-07 02:54:04 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// corners on the board: [1, M+1] * [1, N+1]
int M, N;
int A[210][210];
int f[210][210];
Int solve() {
for (int x = 0; x <= 2*M+4; ++x) for (int y = 0; y <= 2*N+4; ++y) f[x][y] = 0;
// yoko x = 1
for (int y0 = 1, y1 = 1; y0 <= N; y0 = y1) {
for (; y1 <= N && A[1 + 2][y0 + y0+1] == A[1 + 2][y1 + y1+1]; ++y1) {}
if (A[1 + 2][y0 + y0+1] == 4) {
f[1 + 1][y0 + y0+1] = 1;
} else if (A[1 + 2][y0 + y0+1] == 3) {
for (int y = y0; y < y1; y += 2) f[1 + 1][y + y+1] = 1;
}
}
// tate y = 1
for (int x0 = 1, x1 = 1; x0 <= M; x0 = x1) {
for (; x1 <= M && A[x0 + x0+1][1 + 2] == A[x1 + x1+1][1 + 2]; ++x1) {}
if (A[x0 + x0+1][1 + 2] == 4) {
f[x0 + x0+1][1 + 1] = 1;
} else if (A[x0 + x0+1][1 + 2] == 3) {
for (int x = x0; x < x1; x += 2) f[x + x+1][1 + 1] = 1;
}
}
// inflate path
for (int x = 1; x <= M; ++x) for (int y = 1; y <= N; ++y) {
// corner (x, y+1)
f[x + x+1][y+1 + y+1] = f[x + x-1][y+1 + y+1] ^ f[x + x][y+1 + y] ^ f[x + x][y+1 + y+2];
// cell (x+1/2, y+1/2)
f[x+1 + x+1][y + y+1] = (A[x + x+1][y + y+1] & 1) ^ f[x + x][y + y+1] ^ f[x + x+1][y + y] ^ f[x + x+1][y+1 + y+1];
}
// for(int x=0;x<=2*M+4;++x)pv(f[x],f[x]+(2*N+5));cerr<<endl;
for (int x = 1; x <= M+1; ++x) for (int y = 1; y <= N+1; ++y) {
const int sum = f[x + x-1][y + y] + f[x + x][y + y-1] + f[x + x][y + y+1] + f[x + x+1][y + y];
if (!(sum == 0 || sum == 2)) return -1;
}
for (int x = 1; x <= M; ++x) for (int y = 1; y <= N; ++y) {
const int sum = f[x + x][y + y+1] + f[x + x+1][y + y] + f[x + x+1][y+1 + y+1] + f[x+1 + x+1][y + y+1];
if (sum != A[x + x+1][y + y+1]) return -1;
}
Int ans = 0;
for (int x = 0; x <= 2*M+4; ++x) for (int y = 0; y <= 2*N+4; ++y) {
ans += A[x][y] * f[x][y];
}
return ans;
}
int main() {
for (; ~scanf("%d%d", &M, &N); ) {
for (int x = 0; x <= 2*M+4; ++x) for (int y = 0; y <= 2*N+4; ++y) A[x][y] = 0;
for (int x = 1; x <= M; ++x) for (int y = 1; y <= N; ++y) scanf("%d", &A[x + x+1][y + y+1]);
for (int x = 1; x <= M+1; ++x) for (int y = 1; y <= N; ++y) scanf("%d", &A[x + x][y + y+1]);
for (int x = 1; x <= M; ++x) for (int y = 1; y <= N+1; ++y) scanf("%d", &A[x + x+1][y + y]);
// for(int x=0;x<=2*M+4;++x)pv(A[x],A[x]+(2*N+5));cerr<<endl;
const Int ans = solve();
printf("%lld\n", ans);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
1 3 4 2 4 1 1 1 1 1 1 1 1 1 1 1 2 3 3 1 1 1 1 1 1 1 3 3 2 3 2 3 0 3 2 3 2 1 2 3 4 5 6 7 8 9 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12
output:
8 -1 79
result:
ok 3 number(s): "8 -1 79"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
10 8 4 1 0 1 4 1 0 1 1 1 0 0 1 0 1 4 2 3 2 0 0 1 0 1 3 0 3 1 1 4 1 1 2 3 2 1 0 2 1 4 0 1 1 4 2 4 1 2 0 0 0 2 0 1 1 4 0 0 1 4 1 0 0 1 1 0 0 1 0 0 0 1 4 1 0 0 0 0 1 4 2 2 2 1 1 2 1 2 1 1 2 1 1 1 1 1 1 2 1 2 1 2 1 1 1 2 1 1 1 1 2 2 1 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 1 1 1 2 2 1 1 2 1 2 1 2 2 1 2 2 2 1 2 2...
output:
83 -1 45 58 -1 20 -1 99 50 -1 74 50 54 84 45 -1 -1 65 92 -1 -1 -1 62 -1 -1 -1 76 71 -1 58 -1 -1 79 -1 -1 44 82 -1 -1 76 89 64 89 -1 -1 66 105 105 55 -1 34 69 -1 -1 72 -1 -1 -1 82 74 78 87 -1 76 57 -1 27 70 -1 25 63 -1 -1 -1 -1 -1 62 54 26 -1 75 97 58 -1 72 74 91 69 -1 -1 -1 -1 71 54 -1 38 -1 -1 31 57
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3836kb
input:
10 10 4 1 0 1 0 0 0 1 4 1 1 0 2 3 2 0 0 1 1 0 1 1 3 0 3 1 1 2 1 0 4 1 2 3 2 0 0 2 0 0 1 0 1 1 0 0 1 4 1 1 0 1 4 1 1 0 1 1 1 4 1 0 1 1 4 2 4 1 0 2 4 1 0 0 1 0 1 0 1 4 1 0 1 0 0 1 0 0 0 1 0 1 4 1 1 4 1 0 0 0 637156111 681742660 510817373 111758656 948652630 538884415 983688457 17932881 647983164 35833...
output:
-1 -1 21043737050 30487902229 28640676011 27746623861 -1 29925798177 39716826059 -1 -1 28944654742 26641609969 -1 35488019300 -1 35455639372 29491925161 -1 37772627104 -1 26632046838 -1 34208411927 27995559776 -1 34048868167 -1 32255479111 33993240493 -1 29415752041 -1 -1 42199398158 33659861756 330...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
10 10 1 0 3 4 1 0 0 1 4 1 4 1 0 1 0 0 0 1 1 0 2 0 0 0 0 0 1 4 1 1 4 1 1 0 0 0 0 1 1 4 1 1 4 1 1 0 1 0 0 1 0 0 1 1 4 2 4 1 0 0 0 0 0 1 1 1 1 0 1 0 0 0 1 4 2 4 1 1 4 1 0 0 1 1 0 1 1 0 1 0 0 1 4 1 0 1 4 1 0 0 191806095 578350621 94586148 878987116 116996379 772633727 993852293 946198 20267202 141986645...
output:
-1 38729623217 26951474101 -1 -1 -1 30736902461 -1 -1 23783565033 -1 -1 -1 28297033847 -1 33949739466 26384109782 -1 23494204405 -1 28232662888 -1 25982996014 -1 -1 27483619681 -1 29502099525 -1 36816896988 -1 -1 -1 -1 -1 -1 -1 32745875186 37023158077 -1 39920936837 -1 28652554066 28353666251 297520...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 4028kb
input:
20 20 0 0 1 4 1 0 1 4 1 0 0 0 1 4 1 0 1 0 1 0 1 0 1 1 0 0 0 2 0 0 0 1 0 1 0 1 4 2 4 1 4 2 4 1 0 0 1 4 1 0 1 4 1 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 4 1 0 1 4 1 1 0 0 0 0 1 0 1 4 1 1 1 4 0 1 0 0 0 1 1 4 1 1 0 2 3 2 0 1 2 3 2 1 0 0 0 1 0 0 1 1 1 4 2 3 0 3 1 2 2 1 2 2 0 0 1 4 1 1 4 ...
output:
124471183206 119629714411 -1 113995452944 115221644821 131909608891 116607647478 116187304346 129457421816 144776681477 124010517973 125710522181 106834361597 117958058575 -1 122344422932 -1 108953950604 131122674161 -1
result:
ok 20 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
20 20 0 0 0 1 4 1 1 0 1 0 0 0 0 1 0 0 0 0 1 4 0 0 0 0 1 1 4 2 4 1 0 0 1 4 1 0 0 0 0 2 1 0 0 0 1 0 1 0 2 0 0 0 1 1 1 0 1 0 1 4 4 1 0 1 4 1 0 2 3 2 0 1 4 2 4 2 4 1 0 1 1 0 0 0 1 0 1 3 0 2 2 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 3 1 0 3 1 0 0 0 0 0 0 1 4 1 0 0 0 2 3 3 2 0 2 2 0 1 0 0 0 1 0 0 1 4 1 0 1 3 0 2 ...
output:
116878766878 139481018915 138683965076 106949575711 -1 -1 133342410506 -1 140630920056 -1 133472886210 138646438173 122448410426 123175492511 98292343995 96092277317 135630994923 -1 123612073471 -1
result:
ok 20 numbers
Test #7:
score: 0
Accepted
time: 2ms
memory: 4124kb
input:
50 50 0 1 1 4 2 4 1 0 0 1 4 2 4 2 4 2 4 1 1 4 1 1 0 1 4 1 0 0 1 4 1 1 0 0 0 1 4 1 1 4 1 0 1 4 1 1 4 2 4 1 1 4 1 1 0 2 0 0 0 0 1 1 1 0 2 0 2 0 0 1 1 4 1 0 2 0 0 0 0 1 1 4 1 0 0 0 1 0 0 1 0 0 0 2 0 1 1 1 1 1 0 1 0 1 1 4 1 1 0 1 1 4 1 1 4 2 4 1 0 0 0 2 0 2 3 2 0 0 0 1 0 2 0 1 0 0 0 1 0 0 0 0 1 4 2 4 2 ...
output:
-1 724635164718 -1 757490227929
result:
ok 4 number(s): "-1 724635164718 -1 757490227929"
Test #8:
score: 0
Accepted
time: 2ms
memory: 4056kb
input:
50 50 4 2 4 1 0 1 0 0 0 1 1 4 1 0 0 0 0 0 1 4 1 1 4 2 4 1 1 1 4 1 1 4 2 4 2 4 1 1 4 1 0 1 4 1 0 0 0 2 3 2 1 0 1 0 2 3 2 0 2 3 2 1 0 0 0 0 0 0 0 1 0 0 1 1 1 2 3 2 1 0 0 1 0 1 0 1 1 0 2 0 0 0 1 0 0 0 1 3 0 3 0 0 0 1 3 0 3 2 3 0 3 1 0 1 0 0 0 0 0 0 0 0 1 4 2 3 0 3 1 0 1 0 0 0 0 1 4 2 4 1 1 0 0 0 0 0 0 ...
output:
772073639665 -1 734515479069 723004704873
result:
ok 4 number(s): "772073639665 -1 734515479069 723004704873"
Test #9:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
100 100 4 2 4 1 2 3 2 0 0 1 4 1 1 1 4 2 4 1 1 4 1 0 0 0 0 1 4 1 1 4 1 0 1 4 1 0 0 0 0 0 0 1 4 1 0 1 0 1 0 1 0 1 0 0 1 0 1 4 1 1 4 1 1 4 1 1 1 4 1 1 4 1 0 1 4 1 0 0 1 4 2 4 1 1 4 1 1 1 4 1 1 1 4 2 4 1 1 4 2 4 1 1 1 2 2 0 2 2 0 0 1 1 4 1 2 0 2 0 0 1 0 1 0 0 0 1 1 1 0 2 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 4 ...
output:
2814404110082
result:
ok 1 number(s): "2814404110082"
Test #10:
score: 0
Accepted
time: 2ms
memory: 4160kb
input:
100 100 0 1 4 1 1 4 1 1 1 4 1 2 3 3 3 2 0 0 1 0 0 1 1 4 1 1 0 0 1 1 4 2 4 1 0 1 1 4 1 2 3 2 0 0 0 1 4 2 4 2 4 2 4 1 1 0 0 1 4 1 1 1 4 2 4 1 0 0 0 0 0 2 3 2 1 4 2 4 2 4 1 0 0 0 2 3 2 0 2 3 3 3 2 1 4 1 0 0 1 4 0 0 1 0 1 1 1 4 1 2 1 3 0 1 0 2 2 1 4 1 2 3 2 1 1 4 1 1 4 1 2 0 1 0 1 4 1 2 1 3 0 3 1 0 1 0 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 4132kb
input:
100 100 1 4 2 4 1 0 2 3 3 3 3 3 2 0 0 0 2 3 3 3 3 3 2 0 1 4 1 0 1 1 4 2 4 1 1 0 0 0 1 4 1 0 1 0 1 4 1 2 3 2 1 4 1 0 1 1 4 1 0 0 0 0 2 3 2 0 1 4 1 2 3 2 1 4 2 4 1 0 0 0 1 4 1 1 1 4 1 0 0 0 1 1 4 1 1 4 1 0 0 0 0 2 0 2 0 1 3 0 1 1 1 0 3 1 0 2 2 0 1 0 1 0 3 1 1 1 0 1 4 1 1 1 1 1 4 1 0 0 0 1 0 1 4 1 0 1 ...
output:
3005112707429
result:
ok 1 number(s): "3005112707429"
Test #12:
score: 0
Accepted
time: 2ms
memory: 4144kb
input:
100 100 0 2 3 2 1 4 2 4 1 0 1 0 0 1 4 1 1 1 4 1 1 4 1 1 0 2 3 3 3 2 0 1 1 4 1 0 0 1 0 1 4 1 0 1 0 0 1 0 1 4 2 4 1 0 0 2 3 2 0 0 1 4 1 1 0 1 0 0 0 1 4 1 0 1 1 4 1 1 4 1 0 2 3 2 0 0 0 2 3 2 0 1 4 1 1 4 1 1 4 1 1 3 0 3 1 1 0 1 1 1 4 1 0 0 1 1 4 1 1 0 1 1 1 4 2 3 0 1 0 2 3 3 2 1 0 0 1 4 1 0 2 0 1 4 1 1 ...
output:
2774288286857
result:
ok 1 number(s): "2774288286857"
Test #13:
score: 0
Accepted
time: 0ms
memory: 4224kb
input:
100 100 1 4 1 1 4 1 1 1 4 1 1 0 0 0 1 4 1 0 1 4 1 0 0 1 4 2 4 2 4 2 4 2 4 1 2 3 2 1 4 1 0 0 1 0 0 0 0 0 1 4 1 0 1 1 4 1 0 0 1 4 2 4 1 1 1 4 1 0 1 4 1 0 1 4 2 4 1 0 1 4 1 0 0 1 0 1 4 1 0 0 0 0 0 0 0 1 4 1 1 4 1 1 0 0 1 1 4 1 2 1 4 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 3 0 3 1 1 0 0 2 3 2 0 0 ...
output:
2929594083311
result:
ok 1 number(s): "2929594083311"
Test #14:
score: 0
Accepted
time: 2ms
memory: 4236kb
input:
100 100 4 1 0 1 4 2 4 2 4 2 4 2 4 1 0 0 1 4 1 0 0 0 0 1 4 2 4 1 0 0 0 0 1 4 2 4 1 0 1 0 1 0 1 4 1 1 4 1 1 4 1 1 4 1 0 0 0 0 1 0 1 4 1 1 4 2 4 2 4 1 1 4 1 0 0 0 0 2 3 2 0 1 4 1 1 4 1 1 4 1 0 1 0 1 1 4 2 4 2 4 1 1 0 1 1 0 2 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 4 2 4 1 0 1 0 0 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
100 100 0 0 1 4 1 1 4 2 4 1 1 0 0 0 1 4 1 0 0 0 1 4 2 4 1 0 1 4 1 0 0 0 0 1 4 1 1 4 1 0 0 1 0 0 1 0 1 0 0 0 1 4 1 0 0 0 0 0 0 1 4 1 1 0 1 1 4 2 4 1 0 0 0 0 0 1 4 2 4 1 0 0 0 1 4 1 2 3 2 1 4 2 4 2 4 1 0 1 4 1 1 0 0 1 0 0 1 0 1 1 4 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 2 0 0 2 0 0 1 4 1 2 3 3 ...
output:
2872793340511
result:
ok 1 number(s): "2872793340511"
Test #16:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
100 100 1 1 4 1 1 0 1 1 4 2 4 1 1 1 4 1 1 0 0 0 1 1 4 1 0 1 0 0 1 1 4 1 0 0 1 1 4 1 2 3 3 3 2 0 0 0 1 0 1 4 1 2 3 3 3 3 3 2 1 4 2 4 1 0 1 0 2 3 2 0 0 1 4 2 4 1 0 0 0 0 0 1 4 2 4 1 1 0 0 1 0 1 0 1 0 1 4 1 1 4 4 1 1 2 3 3 3 2 1 1 1 1 4 1 2 1 4 1 0 1 4 1 2 0 2 3 2 1 4 1 1 0 0 1 4 1 1 1 3 0 1 0 3 1 0 1 ...
output:
2949049518176
result:
ok 1 number(s): "2949049518176"
Test #17:
score: 0
Accepted
time: 2ms
memory: 4212kb
input:
100 100 1 4 2 4 1 0 0 0 0 1 4 1 0 0 1 4 2 4 1 2 3 2 0 1 4 1 1 4 1 0 0 1 4 1 1 4 2 4 1 1 4 1 0 0 1 0 0 1 4 2 4 2 4 2 4 1 1 4 1 1 4 2 4 1 0 1 0 0 1 0 0 0 1 4 2 4 1 1 4 1 0 1 1 4 1 0 1 0 1 4 2 4 2 4 2 4 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 3 0 3 1 0 1 0 1 1 0 0 0 0 1 0 0 2 0 1 0 0 1 0 0 2 3 2 ...
output:
2781178252547
result:
ok 1 number(s): "2781178252547"
Test #18:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
100 100 4 1 1 4 2 4 1 1 0 0 1 0 1 4 2 4 1 0 0 1 4 2 4 1 2 3 3 3 3 3 2 0 1 4 2 4 2 4 2 4 2 4 2 4 1 1 4 1 0 1 4 1 1 1 4 2 4 1 0 1 4 1 0 0 1 0 0 0 0 0 0 0 0 1 4 2 4 2 4 1 2 3 2 0 1 4 1 1 4 1 1 0 1 0 0 0 0 1 4 1 1 0 0 1 0 1 1 4 1 1 4 1 0 1 0 1 0 0 0 0 1 0 1 2 2 0 1 0 1 0 2 2 0 2 0 2 0 2 0 1 0 1 0 1 0 0 ...
output:
-1
result:
ok 1 number(s): "-1"
Extra Test:
score: 0
Extra Test Passed