QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#478518#8485. Magic Squarerania__#TL 76ms11720kbC++232.9kb2024-07-15 04:05:332024-07-15 04:05:33

Judging History

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

  • [2024-07-15 04:05:33]
  • 评测
  • 测评结果:TL
  • 用时:76ms
  • 内存:11720kb
  • [2024-07-15 04:05:33]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,arr[1010][1010];
map<int,int> mp,mp2;
bool check(){
	int mx=0,mn=MAAX;
	for(int i=0;i<n&&(i==0||mx==mn);i++){
		int sum=0;
		for(int j=0;j<n;j++){
			sum+=arr[i][j];
		}
		mx=max(mx,sum);
		mn=min(mn,sum);
	}
	for(int i=0;i<n&&mx==mn;i++){
		int sum=0;
		for(int j=0;j<n;j++){
			sum+=arr[j][i];
		}
		mx=max(mx,sum);
		mn=min(mn,sum);
	}
	return mx==mn;
}

in main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc=1;
    // cin>>tc;
    while(tc--){
		cin>>n;
		mp.clear();
		mp2.clear();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)
				cin>>arr[i][j];
		}
		vector<int> r,c;
		for(int i=0;i<n;i++){
			int sum=0;
			for(int j=0;j<n;j++){
				sum+=arr[i][j];
			}
			if(mp[sum]<3)
				r.pb(i);
			mp[sum]++;
		}
		for(int i=0;i<n;i++){
			int sum=0;
			for(int j=0;j<n;j++){
				sum+=arr[j][i];
			}
			if(mp2[sum]<3)
				c.pb(i);
			mp2[sum]++;
		}
		for(int i=0;i<r.size();i++){
			for(int j=0;j<c.size();j++){
				for(int k=0;k<r.size();k++){
					for(int l=0;l<c.size();l++){
						swap(arr[r[i]][c[j]],arr[r[k]][c[l]]);
						if(check()){
							cout<<r[i]+1<<" "<<c[j]+1<<"\n"<<r[k]+1<<" "<<c[l]+1<<"\n";
							goto a;
						}
						swap(arr[r[i]][c[j]],arr[r[k]][c[l]]);
					}
				}
			}
		}
		if(c.size()==3){
			for(int i=0;i<r.size();i++){
				for(int j=0;j<r.size();j++){
					int sum1=0;
					for(int k=0;k<n;k++)
						sum1+=arr[r[i]][k];
					int sum2=0;
					for(int k=0;k<n;k++)
						sum2+=arr[r[j]][k];
					for(int k=0;k<n;k++){
						if(sum2+arr[r[i]][k]-arr[r[j]][k]==sum1+arr[r[j]][k]-arr[r[i]][k]){
							swap(arr[r[i]][k],arr[r[j]][k]);
							if(check()){
								cout<<r[i]+1<<" "<<k+1<<"\n"<<r[j]+1<<" "<<k+1<<"\n";
								goto a;
							}
							swap(arr[r[i]][k],arr[r[j]][k]);
						}
					}
				}
			}
		}
		for(int i=0;i<c.size();i++){
			for(int j=0;j<c.size();j++){
				int sum1=0;
				for(int k=0;k<n;k++)
					sum1+=arr[k][c[i]];
				int sum2=0;
				for(int k=0;k<n;k++)
					sum2+=arr[k][c[j]];
				for(int k=0;k<n;k++){
					if(sum2+arr[k][c[i]]-arr[k][c[j]]==sum1+arr[k][c[j]]-arr[k][c[i]]){
						swap(arr[k][c[i]],arr[k][c[j]]);
						if(check()){
							cout<<k+1<<" "<<c[i]+1<<"\n"<<k+1<<" "<<c[j]+1<<"\n";
							goto a;
						}
						swap(arr[k][c[i]],arr[k][c[j]]);
					}
				}
			}
		}
		a:;
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3
6 9 2
3 5 7
8 1 4

output:

1 1
3 3

result:

ok OK

Test #2:

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

input:

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

output:

2 1
2 4

result:

ok OK

Test #3:

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

input:

3
8 1 6
3 5 7
4 2 9

output:

3 2
3 3

result:

ok OK

Test #4:

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

input:

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

output:

2 2
3 3

result:

ok OK

Test #5:

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

input:

5
15 17 1 8 24
3 10 19 21 12
16 23 7 14 6
22 4 13 20 5
9 11 25 2 18

output:

3 5
4 5

result:

ok OK

Test #6:

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

input:

6
14 34 12 5 16 30
27 2 22 9 20 31
18 28 13 36 11 4
19 6 26 1 24 35
10 33 17 29 15 8
23 7 21 32 25 3

output:

3 2
5 4

result:

ok OK

Test #7:

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

input:

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

output:

2 4
3 7

result:

ok OK

Test #8:

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

input:

8
42 22 20 47 19 21 48 41
55 11 13 50 14 12 49 56
57 3 5 58 6 4 63 64
7 59 61 2 62 60 1 8
34 30 28 39 27 29 40 33
15 51 53 10 54 52 9 16
18 46 44 23 43 45 24 17
26 38 36 31 35 37 32 25

output:

1 1
1 7

result:

ok OK

Test #9:

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

input:

9
23 69 1 45 47 34 12 58 80
64 29 51 5 16 75 62 27 40
53 18 31 66 77 55 42 7 49
63 19 41 76 6 65 52 17 30
13 59 81 35 37 24 2 48 70
3 20 71 25 36 14 73 38 60
74 39 61 15 26 4 72 28 50
43 8 21 56 67 54 32 78 10
33 79 11 46 57 44 22 68 9

output:

3 9
6 2

result:

ok OK

Test #10:

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

input:

10
25 86 34 61 75 9 93 68 52 2
1 92 40 67 51 15 99 74 58 8
76 17 65 42 26 90 24 49 33 83
7 98 71 73 57 16 80 55 64 14
13 79 72 29 38 97 6 31 45 95
88 4 47 54 63 22 81 56 70 20
19 85 28 60 69 3 87 62 41 21
100 11 59 36 50 84 18 43 27 77
94 10 53 35 44 78 12 37 46 96
82 23 66 48 32 91 5 30 39 89

output:

4 3
7 9

result:

ok OK

Test #11:

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

input:

10
45 13 31 72 29 79 97 6 95 38
64 7 55 41 73 98 16 80 14 57
70 88 56 47 54 4 22 81 20 63
39 82 30 66 48 23 91 5 89 32
33 76 49 65 85 17 90 24 83 26
71 19 62 28 60 42 3 87 21 69
58 1 74 40 67 92 15 99 8 51
27 100 43 59 36 11 84 18 77 50
52 25 68 34 61 86 9 93 2 75
46 94 37 53 35 10 78 12 96 44

output:

5 5
6 6

result:

ok OK

Test #12:

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

input:

10
35 37 46 44 96 53 10 94 78 12
61 68 52 75 2 34 86 25 9 93
42 49 33 26 83 65 17 76 90 24
48 30 39 32 89 66 23 82 91 5
67 74 58 51 8 77 92 1 15 99
36 43 27 50 40 59 11 100 84 18
73 55 64 57 14 41 98 7 16 80
54 56 70 63 20 47 4 88 22 81
60 62 71 69 21 28 85 19 3 87
29 31 45 38 95 72 79 13 97 6

output:

5 6
6 5

result:

ok OK

Test #13:

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

input:

10
73 16 64 55 80 7 14 41 98 57
63 22 70 56 81 88 20 47 4 54
26 90 33 49 24 76 83 65 17 42
75 9 52 68 93 25 2 34 86 61
44 78 46 37 12 94 96 53 10 35
32 91 39 30 5 82 89 66 23 48
50 84 27 43 18 100 77 59 11 36
51 15 58 74 99 1 8 40 92 67
69 3 71 62 87 19 21 28 85 60
38 97 45 31 6 13 95 72 79 29

output:

1 1
1 10

result:

ok OK

Test #14:

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

input:

10
59 50 84 43 11 18 36 27 77 100
28 69 3 62 85 87 60 71 21 19
47 63 22 56 4 81 54 70 20 88
40 51 15 74 92 99 67 58 8 1
65 26 90 49 17 24 42 33 83 76
34 75 9 68 86 93 61 52 2 25
53 44 78 37 10 12 35 46 96 94
66 32 91 30 23 5 48 39 89 82
41 57 16 55 98 80 73 7 14 64
72 38 97 31 79 6 29 45 95 13

output:

9 8
9 10

result:

ok OK

Test #15:

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

input:

11
26 106 65 11 80 93 119 13 67 39 52
86 34 114 60 19 32 47 73 6 99 101
50 9 78 24 104 117 22 37 91 63 76
14 94 53 120 68 81 107 1 66 27 40
62 21 90 36 116 8 23 49 103 75 88
110 58 17 84 43 45 71 97 30 112 4
74 33 102 48 7 92 35 61 115 87 89
2 82 41 108 56 69 95 121 54 15 28
98 46 5 72 31 44 59 85 1...

output:

7 6
11 5

result:

ok OK

Test #16:

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

input:

99
2266 7116 6712 1660 4894 8128 3783 4086 9542 1155 2874 6510 6308 5904 9239 9340 5197 9037 8633 6106 3379 7015 650 8027 6813 2771 4187 7318 7724 6611 3177 347 5298 5601 8330 953 7926 8835 44 4692 9138 3581 4793 2064 8734 3480 1963 3985 6207 5702 3884 3076 4389 7825 8936 9441 1862 7217 1256 8532 53...

output:

88 41
93 17

result:

ok OK

Test #17:

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

input:

999
391088 566263 801500 495192 630327 958657 43739 394091 289987 884583 840539 148844 567264 161859 919618 770469 316013 21717 237935 771470 97793 575272 287985 381078 836535 844543 445142 810509 847546 802501 769468 3699 55751 955654 717416 103799 968667 20716 322019 574271 165863 500197 727426 78...

output:

178 954
362 629

result:

ok OK

Test #18:

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

input:

999
970378 294699 942350 246651 263668 222627 7412 334741 405 170575 197602 881289 843251 945353 213618 652058 568975 603009 613019 311718 297704 581988 335742 718124 19424 145550 848256 947355 518925 468875 751157 427834 672078 449856 372779 966374 463870 338745 281686 917325 540947 3408 565972 451...

output:

37 959
587 511

result:

ok OK

Test #19:

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

input:

999
92487 937335 7402 228623 93488 926324 186581 276671 564961 198593 364761 594991 834232 396793 264659 857255 292687 466863 348745 281676 9404 232627 748144 438835 695091 548945 328725 567964 324721 498895 597994 658054 312709 694090 410807 568965 554951 260655 676072 489886 395 820218 802200 6730...

output:

194 851
872 424

result:

ok OK

Test #20:

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

input:

1000
311885 688692 311110 311796 311158 311877 311867 688739 688565 688649 311126 688608 688320 311250 311146 311016 311998 311238 311168 311109 311769 688451 688556 688291 311001 311896 688315 688362 688426 688661 311013 311893 688366 688274 311204 311971 311994 688259 311856 311160 311041 688351 3...

output:

15 801
924 790

result:

ok OK

Test #21:

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

input:

1000
363247 636727 363071 363825 363190 636613 363829 636600 636595 636700 363207 636350 636519 636282 363970 363900 636306 363109 636561 636560 636465 636392 363074 363086 363034 636363 636533 363895 363244 363848 363032 363901 363176 636559 636451 636584 363827 363860 636281 363245 363115 363101 3...

output:

15 718
774 877

result:

ok OK

Test #22:

score: 0
Accepted
time: 66ms
memory: 11516kb

input:

1000
531418 531601 531254 468901 468934 531479 468171 468002 468135 531535 468944 531565 468809 468172 468118 468814 468151 468937 468894 531458 531401 531323 468198 468100 468974 468055 531271 531712 531735 468877 531745 531277 468753 468019 468816 468866 468965 468088 531374 531462 531731 468868 5...

output:

521 668
718 635

result:

ok OK

Test #23:

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

input:

1000
519491 480846 519255 519387 480961 519265 519655 480201 480858 480170 519466 519414 519277 480900 519547 480841 480052 519664 519628 519435 480785 519598 519468 519695 519258 480185 519637 519714 480096 480110 480222 519461 519614 519397 480067 480048 519700 519354 480182 480126 480006 480927 4...

output:

75 652
718 257

result:

ok OK

Test #24:

score: 0
Accepted
time: 66ms
memory: 11516kb

input:

1000
981534 981499 18015 18778 18024 981591 981706 18966 981255 18892 18944 18947 981300 18149 18840 18011 981373 981476 18022 18103 981528 18881 18908 981400 981446 18046 18843 18803 18805 981329 981581 18830 18019 18043 18097 981259 18968 981702 18161 18238 981616 18119 981420 981517 981460 981482...

output:

525 443
717 662

result:

ok OK

Test #25:

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

input:

1000
649361 649383 649724 649638 649661 649539 649513 350962 649615 350770 350899 649429 649567 350234 649305 649563 649690 649587 350050 649289 649329 350812 649529 649613 649560 649416 649739 350120 649545 649443 649503 350896 350093 649546 649688 649333 350798 649356 649450 350804 350153 350099 6...

output:

375 235
933 283

result:

ok OK

Test #26:

score: 0
Accepted
time: 52ms
memory: 11648kb

input:

1000
163812 163197 163859 163852 836429 163193 163171 163205 163154 163790 163768 836324 836304 836747 163980 163832 163224 836453 836577 836403 163772 836445 836508 836418 163853 163195 836412 163140 163810 163910 836748 836686 163048 836582 836471 836444 163843 163006 163070 163027 163242 163913 1...

output:

121 322
932 497

result:

ok OK

Test #27:

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

input:

1000
240152 240965 759609 240917 241000 240897 240945 240828 240059 759539 759518 240857 240169 240096 759390 759449 240019 759647 759416 759489 759404 240136 240224 759590 240063 759392 759372 759487 240207 240127 759519 759548 759258 240850 240811 759479 759288 759661 759437 240848 759680 240906 2...

output:

867 305
932 118

result:

ok OK

Test #28:

score: 0
Accepted
time: 46ms
memory: 11512kb

input:

999
324117 278071 277070 37829 498291 544337 70862 95887 336129 297090 104898 444237 250043 54846 311104 153947 149943 134928 210003 691486 746541 78870 945740 390183 676471 638433 539332 375168 874669 31823 611406 422215 564357 191985 730525 147941 535328 785580 978773 265058 262055 909704 919714 3...

output:

1 1
1 2

result:

ok OK

Test #29:

score: 0
Accepted
time: 43ms
memory: 11464kb

input:

999
527654 755882 48173 496623 474601 624751 482609 758885 823950 135260 689816 373498 662789 828955 56181 719846 652779 24149 91216 780907 510637 481608 297422 697824 97222 881007 646773 354479 171296 128253 52177 768895 608735 521648 483610 409534 612739 64189 119244 246371 463590 934060 545672 17...

output:

1 1
1 999

result:

ok OK

Test #30:

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

input:

999
447827 543923 75453 662041 914295 855236 972353 376756 597977 361741 104482 928309 719098 542922 273651 432812 873254 810191 44422 888269 690069 846227 935316 164542 321701 351731 577957 992373 223601 833214 635014 889270 2380 778157 478858 260638 790169 578958 303681 874255 319699 838219 29407 ...

output:

1 499
1 500

result:

ok OK

Test #31:

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

input:

999
294277 133116 259242 965950 670655 185168 678663 865850 760745 664649 535520 694679 686671 808793 314297 464447 748733 88071 425408 548533 92075 56039 945930 705690 255238 404387 805790 386369 962947 422405 740725 389372 111094 500483 754739 50033 406389 317300 954939 508491 262245 838823 905890...

output:

1 998
1 999

result:

ok OK

Test #32:

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

input:

999
370153 983154 220388 320488 396564 89257 799969 152320 452622 573743 86254 747917 760930 162330 995166 778948 937108 826996 901070 462632 972143 481651 834003 140308 74242 626796 711881 756926 965136 192360 232400 312480 75243 184352 3171 286454 992163 336504 608778 442612 610780 732902 204372 5...

output:

1 1
2 2

result:

ok OK

Test #33:

score: -100
Time Limit Exceeded

input:

999
252739 143630 550038 254741 352841 908398 404893 554042 517005 705193 103590 768258 700188 764254 172659 891381 219706 906396 743231 618106 997487 190677 541029 297786 57544 209696 880370 835325 453942 785275 546034 470959 902392 897387 583071 686174 416905 692180 97584 720208 464953 544032 4953...

output:


result: