QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719523#7325. Tube Master IIhos.lyric🐇AC ✓2ms4292kbC++143.6kb2024-11-07 02:53:552024-11-07 02:54:04

Judging History

This is the latest submission verdict.

  • [2024-11-07 02:54:04]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 4292kb
  • [2024-11-07 02:53:55]
  • Submitted

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