QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #51238 | #4633. Coprime Matrices | Jayfeather233 | WA | 2ms | 3760kb | C++ | 1.2kb | 2022-10-01 15:11:34 | 2022-10-01 15:11:36 |
Judging History
answer
#include <iostream>
#include <cstdio>
using namespace std;
int _gcd__(int a,int b){
int t=1;
while(b){
t=a;
a=b;
b=t%b;
}
return a;
}
int gcd(int a,int b){
if(a<b) swap(a,b);
if(b==0) return 1;
return _gcd__(a,b);
}
int vis[100000];
int mp[310][310];
int n,m;
inline int ckR(int x,int y){
return gcd(mp[x][y],mp[x-1][y])==1 || gcd(mp[x][y],mp[x+1][y])==1;
}
inline int ckL(int x,int y){
return gcd(mp[x][y],mp[x][y-1])==1 || gcd(mp[x][y],mp[x][y+1])==1;
}
int dfs(int x,int y){
//printf("AT %d %d\n",x,y);
if(mp[x][y]) return dfs(x,y+1);
if(y==m+1){
return dfs(x+1,1);
}
if(x==n+1){
printf("Yes\n");
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
printf("%d ",mp[i][j]);
}
printf("%d",mp[i][m]);
if(i!=n) printf("\n");
}
//printf("\n");
return true;
}
for(int i=1;i<=n*m;i++){
if(!vis[i]){
vis[i]=1;
mp[x][y]=i;
if((x<=2 || ckR(x-1,y)) && (y<=2 || ckL(x,y-1))){
if(dfs(x,y+1)) return true;
}
vis[i]=0;
mp[x][y]=0;
}
}
return false;
}
int main(){
int x,y,w;
cin>>n>>m>>x>>y>>w;
vis[w]=1;
mp[x][y]=w;
if(!dfs(1,1)) printf("No");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3648kb
input:
3 3 2 1 3
output:
Yes 1 2 4 3 5 6 8 9 7
result:
ok OK, Accepted.
Test #2:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
1 1 1 1 1
output:
Yes 1
result:
ok OK, Accepted.
Test #3:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
8 3 4 2 9
output:
Yes 1 2 3 4 5 6 7 8 11 10 9 12 13 14 15 16 17 19 18 20 21 23 22 24
result:
ok OK, Accepted.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
7 6 7 2 28
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 17 16 19 18 20 21 22 23 24 25 27 26 29 30 31 32 33 34 35 36 37 38 28 39 40 41 42
result:
ok OK, Accepted.
Test #5:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
6 8 1 2 7
output:
Yes 1 7 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 23 20 21 22 25 24 29 26 27 28 31 30 32 33 34 35 36 37 38 41 39 40 42 43 47 44 45 46 48
result:
ok OK, Accepted.
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3760kb
input:
8 8 7 3 56
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 18 23 20 25 21 27 22 24 29 26 28 31 32 30 33 34 35 36 37 38 39 41 40 43 42 47 44 45 46 48 49 50 56 51 52 53 54 55 57 58 59 60 63 62 61 64
result:
wrong answer Co-prime Unsatisfied