QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#627318#9412. Stop the CastleLuckyblockAC ✓1ms3904kbC++203.6kb2024-10-10 15:31:532024-10-10 15:31:54

Judging History

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

  • [2024-10-10 15:31:54]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3904kb
  • [2024-10-10 15:31:53]
  • 提交

answer

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 1e3 + 10;
const int kM = 2e5 + 10;
//=============================================================
int housenum, bannum, n, maxnode;
int edgenum, head[kN], v[kM], ne[kM];
struct Blank {
  int l, r, id;
};

int temp;
std::vector<pii> ans;
std::map<pii, pii> point;
std::map<int, std::set<pii> > rhouse, chouse;
std::map<int, std::vector<Blank> > rnode, cnode;
int match[kN];
bool vis[kN];
//=============================================================
void Add(int u_, int v_) {
  v[++ edgenum] = v_; 
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
bool init() {
  std::cin >> housenum;

  edgenum = 0;
  n = 0, maxnode = 4 * housenum;
  for (int i = 1; i <= maxnode; ++ i) head[i] = match[i] = 0;
  ans.clear(), point.clear();
  rhouse.clear(), chouse.clear(), rnode.clear(), cnode.clear();

  for (int i = 1; i <= housenum; ++ i) {
    int r, c; std::cin >> r >> c;
    rhouse[r].insert(mp(c, 0));
    chouse[c].insert(mp(r, 0));
  }
  std::cin >> bannum;
  for (int i = 1; i <= bannum; ++ i) {
    int r, c; std::cin >> r >> c;
    rhouse[r].insert(mp(c, 1));
    chouse[c].insert(mp(r, 1));
  }

  int flag = 0;
  for (auto [r, s]: rhouse) {
    int last = -1;
    for (auto [c, type]: s) {
      if (last != -1 && type == 0) {
        flag |= (c == last + 1);
        rnode[r].push_back((Blank){last + 1, c - 1, ++ n});
      }
      last = type ? -1 : c;
    }
  }
  for (auto [c, s]: chouse) {
    int last = -1;
    for (auto [r, type]: s) {
      if (last != -1 && type == 0) {
        flag |= (r == last + 1);
        cnode[c].push_back((Blank){last + 1, r - 1, ++ n});
      }
      last = type ? -1 : r;
    }
  }
  if (flag) return true;
  
  for (auto [r, sr]: rnode) {
    for (auto [l1, r1, id1]: sr) {
      for (auto [c, sc]: cnode) {
        if (c < l1 || r1 < c) continue;
        for (auto [l2, r2, id2]: sc) {
          if (r < l2 || r2 < r) continue;
          Add(id1, id2);
          point[mp(id1, id2)] = mp(r, c);
        }
      }
    }
  }
  return false;
}
bool dfs(int u_) {
	for (int i = head[u_]; i; i = ne[i]) {
		int v_ = v[i];
		if (vis[v_]) continue;
		vis[v_] = 1;
		if (!match[v_] || dfs(match[v_])) {
			match[v_] = u_;
			return 1;
		}
	}
	return 0;
}
void solve() {
  for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) vis[j] = 0;
	  dfs(i);
	}
  for (int i = 1; i <= n; ++ i) {
    if (match[i]) {
      ans.push_back(point[mp(match[i], i)]);
      auto [r, c] = ans.back();
      rhouse[r].insert(mp(c, 1));
      chouse[c].insert(mp(r, 1));
    }
  }
  temp = ans.size();

  for (auto [r, s]: rhouse) {
    int last = -1;
    for (auto [c, type]: s) {
      if (last != -1 && type == 0) {
        ans.push_back(mp(r, c - 1));
      }
      last = type ? -1 : c;
    }
  }
  for (auto [c, s]: chouse) {
    int last = -1;
    for (auto [r, type]: s) {
      if (last != -1 && type == 0) {
        ans.push_back(mp(r - 1, c));
      }
      last = type ? -1 : r;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    if (init()) {
      // std::cout << -1 << "----\n";
      std::cout << -1 << "\n"; 
      continue;
    }
    solve();
    std::cout << ans.size() << "\n";
    for (auto [x, y]: ans) std::cout << x << " " << y << "\n";
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3520kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
29 12
41 18
42 38
5
16 13
16 47
31 6
26 26
36 50
0
1
42 10
0
1
43 35
5
1 11
1 40
33 47
44 46
43 44
0
5
27 41
29 40
44 38
10 1
31 15
1
32 12
0
0
0
0
6
23 10
35 34
12 40
23 45
29 33
34 46
0
3
20 31
43 32
34 17
0
-1
3
16 36
25 12
31 39
6
5 5
8 11
6 6
7 7
9 9
10 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

46
94 35
91 61
126 67
349 112
154 138
52 139
185 147
224 153
132 160
311 177
352 186
126 275
270 305
393 307
277 356
334 367
306 374
199 432
187 467
154 496
35 309
187 451
224 431
260 293
261 492
274 111
277 271
311 481
390 366
440 191
453 375
65 4
143 25
351 35
386 61
70 67
80 139
278 186
289 272
4...

result:

ok ok 2 cases (2 test cases)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

20
13
89287395 441913071
89287395 590314987
142917372 582720391
142917372 598813561
232930851 582720391
263974835 468188689
263974835 490702144
543529670 152471388
543529670 219371706
647691663 598813561
772865038 598813561
773363571 482933265
773363571 561453301
8
128947560 120560639
264980960 4742...

output:

8
89287395 590314986
142917372 598813560
263974835 490702143
543529670 219371705
773363571 561453300
232930850 582720391
647691662 598813561
772865037 598813561
7
808969359 818037531
808969359 762966372
808969359 917024052
869847376 354711322
183418802 358274214
808969358 762966373
203395425 8719512...

result:

ok ok 20 cases (20 test cases)

Test #5:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

2
184
35763790 435860426
152681166 443483111
261932524 745277126
261932524 787982418
314305867 342102981
314305867 522593781
314305867 747023891
314305867 811404535
314305867 816914009
314305867 857896659
319901983 797458033
321347896 342102981
332550928 902179526
343207116 914408792
350635050 15515...

output:

160
702209411 328140561
407380694 342102981
469496529 342102981
593934227 357262498
702209411 362635470
673102149 421876106
314305867 435860426
469496529 438907614
561219907 438907614
350635050 443483111
712954986 449645826
702209411 468900569
469496529 526518374
730593611 526518374
812959730 526518...

result:

ok ok 2 cases (2 test cases)

Test #6:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

2
193
78368109 329329995
87932514 657474465
87932514 903492853
94608574 845872655
103602204 88649154
124431127 405860533
145262472 108198774
145262472 907127202
154400439 136367504
165270984 773451933
184157521 409828915
197728547 291882089
197728547 609623645
211750768 843867422
246178069 108396139...

output:

145
412106895 135814914
365329221 136367504
412106895 141752547
365329221 211655411
412106895 211655411
412106895 211732513
246178069 291882089
412106895 291882089
585325539 326063938
365329221 329329995
585325539 381964778
412106895 398630021
197728547 405860533
365329221 409828915
545745067 417008...

result:

ok ok 2 cases (2 test cases)

Test #7:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

2
192
1075648 579875717
1075648 937648715
1393060 191616432
3957616 541362608
3957616 971879257
5415801 541362608
5887448 541362608
5887448 624842533
25767120 610618164
26193206 214214028
26193206 231445627
26727662 374314271
29550509 755417826
29550509 917592925
30033126 610618164
31134588 58188305...

output:

131
622701955 58188305
31134588 191616432
597642622 194741814
746663436 213352628
31134588 231445627
341366249 231445627
417168695 231445627
622701955 231445627
757703054 231445627
954450160 231445627
750293881 239560090
235369723 264208611
250896470 288390629
673815006 322666885
679286177 345284339...

result:

ok ok 2 cases (2 test cases)

Test #8:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

20
14
378192988 147499872
378192988 837331700
449924898 147499872
449924898 837331700
592684636 147499872
592684636 837331700
783332532 147499872
783332532 837331700
378192988 197547597
783332532 197547597
378192988 343857831
783332532 343857831
378192988 576579017
783332532 576579017
2
449924898 19...

output:

15
378192988 197547596
378192988 343857830
378192988 576579016
378192988 837331699
783332532 197547596
783332532 343857830
783332532 576579016
783332532 837331699
449924897 147499872
592684635 147499872
783332531 147499872
783332531 576579017
449924897 837331700
592684635 837331700
783332531 8373317...

result:

ok ok 20 cases (20 test cases)

Test #9:

score: 0
Accepted
time: 1ms
memory: 3904kb

input:

2
200
8623893 3649468
8623893 989134714
24820918 3649468
24820918 989134714
43705451 3649468
43705451 989134714
45500146 3649468
45500146 989134714
58265855 3649468
58265855 989134714
112263159 3649468
112263159 989134714
126496650 3649468
126496650 989134714
137574156 3649468
137574156 989134714
14...

output:

249
24820918 6255307
43705451 11610914
45500146 23366504
58265855 28938721
112263159 31914492
126496650 36029445
137574156 66226935
140089445 84152868
156036789 132710904
170794245 149083019
176576709 174305881
186774359 180413073
194114590 195080121
222368048 231772824
237249112 234663336
250839457...

result:

ok ok 2 cases (2 test cases)

Test #10:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

2
200
2691939 27674656
2691939 984614319
30225807 27674656
30225807 984614319
39388076 27674656
39388076 984614319
55883389 27674656
55883389 984614319
77258752 27674656
77258752 984614319
106874917 27674656
106874917 984614319
144383292 27674656
144383292 984614319
145360776 27674656
145360776 9846...

output:

216
279200011 293316179
347252805 363531956
446662965 376231503
496057717 383623456
514655989 390555088
523731402 441004197
538628510 490065400
562810007 540189713
630132600 545422987
631858791 565468975
643299496 646360861
754008138 861149655
782710197 901945895
2691939 69029839
2691939 160188717
2...

result:

ok ok 2 cases (2 test cases)

Test #11:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

2
200
1005937 7
3412691 7
5764908 7
7897785 7
8061992 7
12801501 7
18529696 7
22574605 7
25203351 7
34574958 7
34998216 7
40928451 7
49792193 7
55962320 7
59632864 7
62353373 7
62611196 7
65346591 7
71459320 7
71550121 7
72215989 7
82584263 7
86119549 7
96204862 7
96940713 7
97693112 7
102067050 7
1...

output:

199
3412690 7
5764907 7
7897784 7
8061991 7
12801500 7
18529695 7
22574604 7
25203350 7
34574957 7
34998215 7
40928450 7
49792192 7
55962319 7
59632863 7
62353372 7
62611195 7
65346590 7
71459319 7
71550120 7
72215988 7
82584262 7
86119548 7
96204861 7
96940712 7
97693111 7
102067049 7
105454642 7
1...

result:

ok ok 2 cases (2 test cases)

Extra Test:

score: 0
Extra Test Passed