QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138907 | #4633. Coprime Matrices | Sommohito# | WA | 1ms | 3488kb | C++20 | 3.1kb | 2023-08-12 13:34:48 | 2023-08-12 13:34:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#ifdef APURBA
#include "DEBUG_TEMPLATE.h"
#else
#define HERE
#define debug(args...)
#endif
#define ALL(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=305;
int n,m,x,y,w;
int ans[N][N];
bool ok(int i,int j)
{
if(ans[i][j]==0) return true;
int row=0,col=0;
if(i<1||i>=n-1) row=2;
else
{
if(__gcd(ans[i-1][j],ans[i][j])==1||ans[i-1][j]==0) row++;
if(__gcd(ans[i+1][j],ans[i][j])==1||ans[i+1][j]==0) row++;
}
if(j<1||j>=m-1) col=2;
else
{
if(__gcd(ans[i][j-1],ans[i][j])==1||ans[i][j-1]==0) col++;
if(__gcd(ans[i][j+1],ans[i][j])==1||ans[i][j+1]==0) col++;
}
// debug(i,j,ans[i][j]);
return row>=1&&col>=1;
}
void build(vector<pair<int,int>>& pos,vector<int>& all,set<int>& done,int which,int idx)
{
// debug(done,pos,all,which,idx);
// for(int i=0; i<n; i++)
// {
// for(int j=0; j<m; j++)
// {
// cout<<ans[i][j]<<' ';
// }
// cout<<"\n";
// }
if(done.size()==n*m)
{
cout<<"Yes\n";
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cout<<ans[i][j]<<' ';
}
cout<<"\n";
}
exit(0);
}
int X=pos[idx].first,Y=pos[idx].second;
while(true)
{
int W=all[which];
which=(which+1)%(int)all.size();
if(done.find(W)!=done.end()) continue;
ans[X][Y]=W;
if(ok(x,y)&&ok(X,Y)&&ok(X-1,Y)&&ok(X+1,Y)&&ok(X,Y-1)&&ok(X,Y+1))
{
done.insert(W);
build(pos,all,done,which,idx+1);
done.erase(W);
}
ans[X][Y]=0;
}
}
void TEST_CASES()
{
cin>>n>>m>>x>>y>>w;
x--;
y--;
ans[x][y]=w;
vector<int>even,odd;
for(int i=2; i<=n*m; i+=2)
{
if(i==w) continue;
even.push_back(i);
}
for(int i=1; i<=n*m; i+=2)
{
if(i==w) continue;
odd.push_back(i);
}
shuffle(even.begin(),even.end(),rng);
shuffle(odd.begin(),odd.end(),rng);
vector<int>all;
for(int u:even) all.push_back(u);
for(int u:odd) all.push_back(u);
// debug(all);
vector<pair<int,int>>pos;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(i==x&&j==y) continue;
if((i+j)%2==0) pos.push_back({i,j});
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(i==x&&j==y) continue;
if((i+j)%2==1) pos.push_back({i,j});
}
}
set<int>done= {w};
build(pos,all,done,0,0);
cout<<"No\n";
}
/*
*/
int32_t main()
{
#ifndef APURBA
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
//freopen("input.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t=1;
//cin>>t;
while(t--)
{
TEST_CASES();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3488kb
input:
3 3 2 1 3
output:
Yes 4 9 6 3 2 1 8 5 7
result:
wrong output format Expected EOLN