QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#332503#6305. Chinese CheckerMesSimonFallonWA 7ms3788kbC++142.0kb2024-02-19 15:27:222024-02-19 15:27:22

Judging History

你现在查看的是最新测评结果

  • [2024-02-19 15:27:22]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3788kb
  • [2024-02-19 15:27:22]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0; i < n; ++i)
#define for1(i,n) for(int i=1; i <= n; ++i)
#define fore(i,l,r) for(int i=l; i <= r; ++i)
#define pb push_back
#define el '\n'
#define fi first
#define se second
#define sz(v) int(v.size())
#define D(v) cout << #v << " : " << v << el;

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
vi st{ 4, 4, 4, 4, 0,  1,  2,  3,  4,  3,  2,  1,  0, 5, 6, 7, 8 };
vi an{ 1, 2, 3, 4, 13, 12, 11, 10, 9, 10, 11, 12, 13, 4, 3, 2, 1};
vii pos;
typedef array<int, 3> i3;
set<i3> dp;
int g[30][30];

bool check(int i, int j){
  if(i < 0 || i >= sz(st)) return 0;
  return st[i] <= j && j < st[i] + an[i];
}

vector<ii> dir{
  {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}
};

void dfs(i3 cur){
  if(dp.count(cur)) return;
  dp.insert(cur);
  i3 pre = cur;
  auto [idx, i, j] = cur;
  // D(idx); D(i); D(j); cout << el;
  for(auto&[di, dj]: dir){
    int ni = i, nj = j, iters = 0;
    bool melo = 0;
    while(++iters){
      ni += di,  nj += dj;
      if(!check(ni, nj)) break;
      if(g[ni][nj]){
        melo = 1; break;
      }
    }
    if(melo){
      forn(it, iters){
        ni += di,  nj += dj;
        if(!check(ni, nj) || (g[ni][nj] && it < iters-1)){
          melo = 0; break;
        }
      }
      // D(iters); D(check(ni, nj));D(g[ni][nj]);
      if(melo && !g[ni][nj]){
        dfs({idx, ni, nj});
      }
    }
  }
  // cur = pre;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    pos.resize(n);
    forn(i, n){
      int r, c; cin >> r >> c;
      --r, --c;
      pos[i] = {r, st[r] + c};
      g[r][st[r]+c] = i+1;
    }

    forn(i, n){
      g[pos[i].fi][pos[i].se] = 0;
      i3 cur{i+1, pos[i].fi, pos[i].se};
      dfs(cur);
      g[pos[i].fi][pos[i].se] = i+1;
    }
    cout << sz(dp) - n << el;
    dp.clear();
    forn(i, 30) forn(j, 30) g[i][j] = 0;
  }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

input:

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

output:

0
1
2
6
13

result:

ok 5 number(s): "0 1 2 6 13"

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 3788kb

input:

100
81
1 1
16 1
11 4
13 8
12 3
12 12
11 1
4 2
9 5
8 10
5 5
9 7
3 2
14 1
7 11
13 7
10 2
8 3
9 8
10 6
12 10
6 7
11 2
7 3
13 12
8 6
17 1
10 5
5 12
13 9
13 1
9 4
5 10
11 8
13 4
5 4
9 1
7 8
5 6
13 13
5 1
9 3
8 8
8 5
13 2
13 5
11 3
9 2
6 4
3 3
8 2
13 11
8 7
5 7
6 10
11 9
10 3
11 10
6 3
7 1
4 4
15 2
7 2
3 ...

output:

196
457
186
499
368
260
154
38
275
86
1
118
87
69
20
117
292
226
10
186
76
158
216
16
95
274
260
307
141
91
183
278
24
7
122
142
255
313
47
154
263
47
10
68
77
183
29
133
368
105
154
236
0
109
94
27
21
5
68
184
157
27
363
173
285
4
47
0
257
95
88
338
0
302
70
92
47
273
63
22
444
342
4
217
94
0
149
2...

result:

wrong answer 1st numbers differ - expected: '190', found: '196'