QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785401#4952. Cutting with LasersLaVuna47#AC ✓76ms36184kbC++202.9kb2024-11-26 17:50:092024-11-26 17:50:10

Judging History

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

  • [2024-11-26 17:50:10]
  • 评测
  • 测评结果:AC
  • 用时:76ms
  • 内存:36184kb
  • [2024-11-26 17:50:09]
  • 提交

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

#define MAX_N 2000

int M[MAX_N][MAX_N];
int vis[MAX_N][MAX_N];

vector<pii> D = {{0,-1}, {0, 1}, {1, 0}, {-1,0}};

int unset(int num, int p)
{
	return num & (~(1 << p));
}

void unconnect(pii a, pii b)
{
	if(a.x == b.x)
	{
		for(int i = min(a.y, b.y); i < max(a.y, b.y); ++i)
		{
			if(a.x-1 >= 0)
			{
				M[a.x][i] = unset(M[a.x][i], 3);
				M[a.x-1][i] = unset(M[a.x-1][i], 2);
			}
		}
	}
	else if(a.y == b.y)
	{
		for(int i = min(a.x, b.x); i < max(a.x, b.x); ++i)
		{
			if(a.y-1 >= 0)
			{
				M[i][a.y] = unset(M[i][a.y], 0);
				M[i][a.y-1] = unset(M[i][a.y-1], 1);
			}
		}
	}
	else assert(false);
}

void dfs(pii v, int marker)
{
	queue<pii> Q;
	Q.push(v);
	vis[v.x][v.y] = marker;
	while(!Q.empty())
	{
		v = Q.front();
		Q.pop();
		auto [x, y] = v;
		FOR(i,0,sz(D))
		{
			auto [dx, dy] = D[i];
			if(((M[x][y] >> i) & 1) && x+dx >= 0 && x+dx < MAX_N && y+dy >= 0 && y+dy < MAX_N && !vis[x+dx][y+dy])
			{
				vis[x+dx][y+dy] = marker;
				Q.push({x+dx, y+dy});
			}
		}
	}

}

int solve()
{
	int n;
	if(!(cin >> n))
		return 1;
	FOR(i,0,MAX_N)
	{
		FOR(j,0,MAX_N)
		{
			M[i][j] = 0b1111;
		}
	}
	vector<pii> p(n+1);
	FOR(i,0,n+1) cin >> p[i].x >> p[i].y;

	FOR(i,0,n)
	{
		unconnect(p[i], p[i+1]);
	}
	int marker = 1;
	FOR(i,0,MAX_N)
	{
		FOR(j,0,MAX_N)
		{
			if(!vis[i][j])
			{
				dfs({i,j}, marker++);
			}
		}
	}
	vector<int> S(marker, 0);
	FOR(i,0,MAX_N)
	{
		FOR(j,0,MAX_N)
		{
			S[vis[i][j]] += 1;
		}
	}
	sort(rall(S));
	cout << S[1] << "\n";
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 53ms
memory: 34880kb

input:

8
2 1
7 1
7 4
3 4
3 2
5 2
5 6
2 6
2 1

output:

17

result:

ok single line: '17'

Test #2:

score: 0
Accepted
time: 49ms
memory: 34884kb

input:

14
1 1
8 1
8 6
6 6
6 2
2 2
2 4
7 4
7 5
3 5
3 3
4 3
4 6
1 6
1 1

output:

21

result:

ok single line: '21'

Test #3:

score: 0
Accepted
time: 47ms
memory: 34872kb

input:

4
1 1
1 1000
1000 1000
1000 1
1 1

output:

998001

result:

ok single line: '998001'

Test #4:

score: 0
Accepted
time: 55ms
memory: 34824kb

input:

4
1 1
1 2
2 2
2 1
1 1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 53ms
memory: 35084kb

input:

6
1000 1000
1000 500
1 500
1 1
500 1
500 1000
1000 1000

output:

250000

result:

ok single line: '250000'

Test #6:

score: 0
Accepted
time: 54ms
memory: 35032kb

input:

12
530 101
530 89
636 89
636 52
180 52
180 906
236 906
236 910
828 910
828 423
69 423
530 423
530 101

output:

315352

result:

ok single line: '315352'

Test #7:

score: 0
Accepted
time: 42ms
memory: 34808kb

input:

18
474 189
474 32
477 32
477 359
715 359
715 698
935 698
935 447
939 447
939 984
1000 984
1000 988
305 988
305 992
590 992
590 31
660 31
660 189
474 189

output:

144833

result:

ok single line: '144833'

Test #8:

score: 0
Accepted
time: 51ms
memory: 34808kb

input:

16
459 407
807 407
807 187
892 187
892 229
946 229
946 219
275 219
275 187
558 187
558 622
956 622
956 65
998 65
998 40
459 40
459 407

output:

197167

result:

ok single line: '197167'

Test #9:

score: 0
Accepted
time: 55ms
memory: 34824kb

input:

12
281 573
281 971
156 971
156 988
897 988
897 997
989 997
989 998
312 998
312 601
74 601
74 573
281 573

output:

14122

result:

ok single line: '14122'

Test #10:

score: 0
Accepted
time: 65ms
memory: 34944kb

input:

46
489 450
489 205
322 205
322 178
306 178
306 415
291 415
291 886
80 886
80 741
43 741
43 479
36 479
36 287
32 287
32 752
681 752
681 592
788 592
788 32
23 32
23 4
17 4
17 641
532 641
532 525
301 525
301 380
632 380
632 139
118 139
118 298
747 298
747 185
818 185
818 425
181 425
181 333
960 333
960...

output:

149424

result:

ok single line: '149424'

Test #11:

score: 0
Accepted
time: 59ms
memory: 34916kb

input:

36
526 139
213 139
213 118
101 118
101 31
49 31
49 725
33 725
33 147
18 147
18 136
229 136
229 154
174 154
174 116
65 116
65 94
42 94
42 79
337 79
337 53
239 53
239 46
201 46
201 40
88 40
88 19
313 19
313 12
409 12
409 11
523 11
523 938
902 938
902 766
902 139
526 139

output:

302821

result:

ok single line: '302821'

Test #12:

score: 0
Accepted
time: 55ms
memory: 34888kb

input:

38
776 919
776 464
699 464
699 405
971 405
971 748
981 748
981 985
1000 985
1000 996
223 996
223 999
198 999
198 798
87 798
87 361
52 361
52 322
186 322
186 678
132 678
132 566
2 566
2 125
252 125
252 684
690 684
690 456
678 456
678 47
389 47
389 7
918 7
918 990
559 990
559 991
637 991
637 919
776 919

output:

443276

result:

ok single line: '443276'

Test #13:

score: 0
Accepted
time: 57ms
memory: 34944kb

input:

44
149 120
54 120
54 711
428 711
428 484
322 484
322 535
444 535
444 343
64 343
64 180
13 180
13 207
6 207
6 831
928 831
928 341
968 341
968 777
989 777
989 576
561 576
561 788
963 788
963 464
987 464
987 243
661 243
661 975
99 975
99 998
179 998
179 1000
73 1000
73 530
801 530
801 38
961 38
961 712...

output:

273757

result:

ok single line: '273757'

Test #14:

score: 0
Accepted
time: 56ms
memory: 34884kb

input:

42
675 26
675 16
795 16
795 182
617 182
617 40
451 40
451 9
237 9
237 8
132 8
132 980
693 980
693 987
981 987
981 303
15 303
15 35
64 35
64 29
12 29
12 13
557 13
557 925
772 925
772 871
854 871
854 922
840 922
840 974
890 974
890 724
362 724
362 915
74 915
74 771
85 771
85 586
39 586
39 873
438 873
...

output:

277613

result:

ok single line: '277613'

Test #15:

score: 0
Accepted
time: 60ms
memory: 34828kb

input:

180
36 745
946 745
946 895
953 895
953 389
203 389
203 605
644 605
644 350
66 350
66 89
39 89
39 937
726 937
726 256
869 256
869 3
895 3
895 1
870 1
870 526
999 526
999 17
62 17
62 2
469 2
469 1
786 1
786 704
168 704
168 917
55 917
55 417
29 417
29 296
375 296
375 853
169 853
169 916
782 916
782 618...

output:

68117

result:

ok single line: '68117'

Test #16:

score: 0
Accepted
time: 58ms
memory: 34860kb

input:

118
417 598
128 598
128 43
358 43
358 35
966 35
966 914
204 914
204 991
801 991
801 996
863 996
863 959
519 959
519 125
880 125
880 135
807 135
807 234
653 234
653 825
212 825
212 891
10 891
10 925
776 925
776 873
76 873
76 807
354 807
354 688
307 688
307 903
616 903
616 934
864 934
864 990
802 990
...

output:

72932

result:

ok single line: '72932'

Test #17:

score: 0
Accepted
time: 54ms
memory: 35088kb

input:

184
815 664
630 664
630 392
161 392
161 556
115 556
115 888
67 888
67 454
178 454
178 47
156 47
156 35
166 35
166 800
71 800
71 166
24 166
24 63
6 63
6 522
560 522
560 987
837 987
837 459
882 459
882 324
489 324
489 565
430 565
430 538
621 538
621 295
418 295
418 402
573 402
573 191
294 191
294 649
...

output:

35586

result:

ok single line: '35586'

Test #18:

score: 0
Accepted
time: 54ms
memory: 34880kb

input:

102
413 810
908 810
908 593
765 593
765 384
381 384
381 12
285 12
285 114
43 114
43 21
3 21
3 311
798 311
798 552
364 552
364 623
821 623
821 938
864 938
864 913
974 913
974 964
366 964
366 970
605 970
605 999
490 999
490 706
129 706
129 598
565 598
565 451
67 451
67 578
961 578
961 964
574 964
574 ...

output:

52627

result:

ok single line: '52627'

Test #19:

score: 0
Accepted
time: 55ms
memory: 34792kb

input:

300
472 994
472 455
598 455
598 48
13 48
13 685
11 685
11 305
6 305
6 384
2 384
2 117
847 117
847 296
1000 296
1000 288
671 288
671 152
902 152
902 43
965 43
965 20
999 20
999 8
1000 8
1000 778
676 778
676 823
290 823
290 455
14 455
14 631
797 631
797 110
860 110
860 278
964 278
964 187
980 187
980 ...

output:

19731

result:

ok single line: '19731'

Test #20:

score: 0
Accepted
time: 57ms
memory: 34896kb

input:

436
563 513
563 696
926 696
926 359
956 359
956 785
525 785
525 861
937 861
937 565
899 565
899 980
33 980
33 358
270 358
270 660
46 660
46 964
751 964
751 665
572 665
572 231
83 231
83 241
28 241
28 41
22 41
22 937
3 937
3 997
2 997
2 999
1 999
1 634
506 634
506 891
67 891
67 751
55 751
55 51
48 51...

output:

16698

result:

ok single line: '16698'

Test #21:

score: 0
Accepted
time: 63ms
memory: 34884kb

input:

298
616 405
187 405
187 563
864 563
864 120
833 120
833 44
41 44
41 8
369 8
369 6
236 6
236 2
148 2
148 1
96 1
96 857
23 857
23 338
21 338
21 11
12 11
12 445
495 445
495 115
577 115
577 34
831 34
831 300
453 300
453 549
621 549
621 577
533 577
533 538
969 538
969 404
953 404
953 715
961 715
961 350
...

output:

23726

result:

ok single line: '23726'

Test #22:

score: 0
Accepted
time: 57ms
memory: 35060kb

input:

362
587 6
587 4
287 4
287 718
69 718
69 401
20 401
20 177
60 177
60 576
704 576
704 605
862 605
862 714
903 714
903 809
353 809
353 294
785 294
785 60
542 60
542 802
274 802
274 979
242 979
242 1000
165 1000
165 971
770 971
770 991
334 991
334 998
667 998
667 1000
363 1000
363 767
201 767
201 436
14...

output:

17195

result:

ok single line: '17195'

Test #23:

score: 0
Accepted
time: 60ms
memory: 35080kb

input:

624
544 742
11 742
11 292
6 292
6 951
350 951
350 986
739 986
739 990
953 990
953 962
749 962
749 984
838 984
838 994
937 994
937 289
941 289
941 646
963 646
963 171
986 171
986 8
990 8
990 3
993 3
993 687
285 687
285 604
757 604
757 807
433 807
433 974
599 974
599 986
787 986
787 998
938 998
938 24...

output:

12926

result:

ok single line: '12926'

Test #24:

score: 0
Accepted
time: 56ms
memory: 35108kb

input:

602
45 466
45 927
994 927
994 413
999 413
999 577
193 577
193 543
430 543
430 737
373 737
373 487
456 487
456 412
763 412
763 72
991 72
991 13
997 13
997 238
501 238
501 130
176 130
176 171
586 171
586 271
136 271
136 731
216 731
216 914
211 914
211 958
26 958
26 961
291 961
291 180
739 180
739 74
2...

output:

5689

result:

ok single line: '5689'

Test #25:

score: 0
Accepted
time: 50ms
memory: 34840kb

input:

740
585 8
912 8
912 766
943 766
943 806
737 806
737 893
445 893
445 485
829 485
829 753
988 753
988 982
1000 982
1000 998
849 998
849 467
946 467
946 618
270 618
270 630
720 630
720 637
169 637
169 475
140 475
140 788
68 788
68 988
450 988
450 177
37 177
37 57
324 57
324 459
610 459
610 324
651 324
...

output:

3280

result:

ok single line: '3280'

Test #26:

score: 0
Accepted
time: 54ms
memory: 35208kb

input:

1798
306 326
396 326
396 942
700 942
700 951
785 951
785 996
467 996
467 1000
396 1000
396 764
85 764
85 681
223 681
223 54
809 54
809 43
719 43
719 26
970 26
970 10
163 10
163 3
975 3
975 887
371 887
371 964
763 964
763 329
890 329
890 10
641 10
641 67
42 67
42 43
184 43
184 903
988 903
988 567
999...

output:

1786

result:

ok single line: '1786'

Test #27:

score: 0
Accepted
time: 59ms
memory: 34892kb

input:

1948
311 112
311 962
883 962
883 148
357 148
357 971
226 971
226 410
107 410
107 789
140 789
140 994
269 994
269 632
147 632
147 724
63 724
63 925
649 925
649 34
200 34
200 387
651 387
651 367
849 367
849 1000
895 1000
895 506
193 506
193 885
368 885
368 354
11 354
11 262
876 262
876 249
1000 249
10...

output:

676

result:

ok single line: '676'

Test #28:

score: 0
Accepted
time: 61ms
memory: 35140kb

input:

4854
246 588
42 588
42 382
98 382
98 233
998 233
998 173
954 173
954 418
971 418
971 551
922 551
922 717
577 717
577 656
506 656
506 648
197 648
197 928
521 928
521 120
889 120
889 109
923 109
923 87
122 87
122 551
736 551
736 691
686 691
686 820
731 820
731 875
990 875
990 49
996 49
996 265
999 265...

output:

180

result:

ok single line: '180'

Test #29:

score: 0
Accepted
time: 76ms
memory: 36184kb

input:

9632
517 210
517 666
66 666
66 606
19 606
19 335
503 335
503 398
1000 398
1000 264
520 264
520 214
348 214
348 119
978 119
978 131
920 131
920 23
490 23
490 18
199 18
199 13
72 13
72 2
11 2
11 881
451 881
451 109
741 109
741 592
205 592
205 75
93 75
93 37
16 37
16 698
12 698
12 7
810 7
810 3
829 3
8...

output:

66

result:

ok single line: '66'