QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138907#4633. Coprime MatricesSommohito#WA 1ms3488kbC++203.1kb2023-08-12 13:34:482023-08-12 13:34:49

Judging History

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

  • [2023-08-12 13:34:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3488kb
  • [2023-08-12 13:34:48]
  • 提交

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