QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #478475 | #8485. Magic Square | rania__# | TL | 3ms | 3868kb | C++23 | 1.8kb | 2024-07-15 00:29:17 | 2024-07-15 00:29:17 |
Judging History
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(){
vector<int> v;
for(int i=0;i<n;i++){
int sum=0;
for(int j=0;j<n;j++){
sum+=arr[i][j];
}
v.pb(sum);
}
for(int i=0;i<n;i++){
int sum=0;
for(int j=0;j<n;j++){
sum+=arr[j][i];
}
v.pb(sum);
}
sort(v.begin(),v.end());
return v[0]==v.back();
}
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]<50)
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]<50)
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]]);
}
}
}
}
a:;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
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: 3584kb
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: 3568kb
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: 3628kb
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: 0ms
memory: 3580kb
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: 3580kb
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: 3620kb
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: 3632kb
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: 1ms
memory: 3696kb
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: 1ms
memory: 3820kb
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: 1ms
memory: 3600kb
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: 2ms
memory: 3540kb
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: 3824kb
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: 2ms
memory: 3676kb
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: 3ms
memory: 3604kb
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: -100
Time Limit Exceeded
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...