QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#81968	#5575. Knight's Tour Redux	upsolveupsolve	AC ✓	17ms	4064kb	C++20	2.4kb	2023-02-26 19:34:18	2023-02-26 19:35:55

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-26 19:35:55]
评测

测评结果：AC
用时：17ms
内存：4064kb

查看

[2023-02-26 19:34:18]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;

vector<int> dh={-3,-1,1,3,3,1,-1,-3},dw={1,3,3,1,-1,-3,-3,-1};
/*
bool useh[13],usew[13];
int N;
vector<int> D;

void DFS(int h,int w,int t){
    if(h<0||h>=N||w<0||w>=N) return;
    if(useh[h]||usew[w]) return;
    useh[h]=true;
    usew[w]=true;
    if(t==N-1){
        for(int x:D) cout<<x<<",";
        cout<<endl;
        return;
    }
    
    for(int k=0;k<8;k++){
        D.push_back(k);
        DFS(h+dh[k],w+dw[k],t+1);
        D.pop_back();
    }
    
    useh[h]=false;
    usew[w]=false;
}
*/
int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    /*
    for(N=5;N<=10;N++){
        memset(useh,0,sizeof(useh));
        memset(usew,0,sizeof(usew));
        D.clear();
        DFS(0,2,0);
    }
    */
    vector<vector<int>> base;
    base.push_back({3,5,0,2});
    base.push_back({2,4,5,7,2});
    base.push_back({2,3,5,0,5,4});
    base.push_back({2,3,3,6,6,7,2});
    base.push_back({2,2,4,4,6,0,6,4});
    base.push_back({2,2,3,5,3,6,6,7,1});
    
    vector<int> mov={3,5,0,2,3,2};
    
    int N;cin>>N;
    if(N==1){
        cout<<"POSSIBLE\n";
        cout<<"1 1\n";
        return 0;
    }
    if(N<=4){
        cout<<"IMPOSSIBLE\n";
        return 0;
    }
    
    int type=(N-5)%6,syo=(N-5)/6;
    int h=0,w=2;
    vector<pair<int,int>> ans;
    for(int t=0;t<syo;t++){
        for(int k:mov){
            ans.push_back(mp(h,w));
            h+=dh[k];
            w+=dw[k];
        }
    }
    
    for(int k:base[type]){
        ans.push_back(mp(h,w));
        h+=dh[k];
        w+=dw[k];
    }
    
    ans.push_back(mp(h,w));
    
    for(int i=0;i+1<si(ans);i++){
        int h=abs(ans[i+1].fi-ans[i].fi),w=abs(ans[i+1].se-ans[i].se);
        if(h>w) swap(h,w);
        assert(h==1&&w==3);
    }
    
    cout<<"POSSIBLE\n";
    
    for(auto [a,b]:ans) cout<<a+1<<" "<<b+1<<"\n";
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3336kb

input:

output:

POSSIBLE
1 1

result:

ok answer = 1

Test #2:

score: 0

Accepted

time: 2ms

memory: 3408kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #3:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #4:

score: 0

Accepted

time: 1ms

memory: 3280kb

input:

output:

IMPOSSIBLE

result:

ok answer = 0

Test #5:

score: 0

Accepted

time: 2ms

memory: 3336kb

input:

output:

POSSIBLE
1 3
4 4
5 1
2 2
3 5

result:

ok answer = 1

Test #6:

score: 0

Accepted

time: 0ms

memory: 3288kb

input:

output:

POSSIBLE
1 3
2 6
5 5
6 2
3 1
4 4

result:

ok answer = 1

Test #7:

score: 0

Accepted

time: 0ms

memory: 3284kb

input:

output:

POSSIBLE
1 3
2 6
5 7
6 4
3 5
4 2
7 1

result:

ok answer = 1

Test #8:

score: 0

Accepted

time: 0ms

memory: 3288kb

input:

output:

result:

ok answer = 1

Test #9:

score: 0

Accepted

time: 0ms

memory: 3280kb

input:

output:

result:

ok answer = 1

Test #10:

score: 0

Accepted

time: 2ms

memory: 3280kb

input:

output:

result:

ok answer = 1

Test #11:

score: 0

Accepted

time: 2ms

memory: 3336kb

input:

output:

result:

ok answer = 1

Test #12:

score: 0

Accepted

time: 2ms

memory: 3408kb

input:

output:

result:

ok answer = 1

Test #13:

score: 0

Accepted

time: 1ms

memory: 3296kb

input:

output:

result:

ok answer = 1

Test #14:

score: 0

Accepted

time: 2ms

memory: 3412kb

input:

output:

result:

ok answer = 1

Test #15:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

output:

result:

ok answer = 1

Test #16:

score: 0

Accepted

time: 2ms

memory: 3352kb

input:

output:

result:

ok answer = 1

Test #17:

score: 0

Accepted

time: 2ms

memory: 3260kb

input:

output:

result:

ok answer = 1

Test #18:

score: 0

Accepted

time: 1ms

memory: 3304kb

input:

output:

result:

ok answer = 1

Test #19:

score: 0

Accepted

time: 2ms

memory: 3292kb

input:

output:

result:

ok answer = 1

Test #20:

score: 0

Accepted

time: 2ms

memory: 3280kb

input:

output:

result:

ok answer = 1

Test #21:

score: 0

Accepted

time: 6ms

memory: 3996kb

input:

output:

result:

ok answer = 1

Test #22:

score: 0

Accepted

time: 17ms

memory: 3948kb

input:

output:

result:

ok answer = 1

Test #23:

score: 0

Accepted

time: 11ms

memory: 3920kb

input:

output:

result:

ok answer = 1

Test #24:

score: 0

Accepted

time: 17ms

memory: 4000kb

input:

output:

result:

ok answer = 1

Test #25:

score: 0

Accepted

time: 6ms

memory: 4004kb

input:

output:

result:

ok answer = 1

Test #26:

score: 0

Accepted

time: 13ms

memory: 4048kb

input:

output:

result:

ok answer = 1

Test #27:

score: 0

Accepted

time: 8ms

memory: 3892kb

input:

output:

result:

ok answer = 1

Test #28:

score: 0

Accepted

time: 11ms

memory: 3944kb

input:

output:

result:

ok answer = 1

Test #29:

score: 0

Accepted

time: 13ms

memory: 4004kb

input:

output:

result:

ok answer = 1

Test #30:

score: 0

Accepted

time: 14ms

memory: 4056kb

input:

output:

result:

ok answer = 1

Test #31:

score: 0

Accepted

time: 10ms

memory: 4048kb

input:

output:

result:

ok answer = 1

Test #32:

score: 0

Accepted

time: 5ms

memory: 4032kb

input:

output:

result:

ok answer = 1

Test #33:

score: 0

Accepted

time: 0ms

memory: 3472kb

input:

output:

result:

ok answer = 1

Test #34:

score: 0

Accepted

time: 4ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #35:

score: 0

Accepted

time: 6ms

memory: 3468kb

input:

output:

result:

ok answer = 1

Test #36:

score: 0

Accepted

time: 2ms

memory: 3520kb

input:

output:

result:

ok answer = 1

Test #37:

score: 0

Accepted

time: 10ms

memory: 3924kb

input:

output:

result:

ok answer = 1

Test #38:

score: 0

Accepted

time: 13ms

memory: 4048kb

input:

output:

result:

ok answer = 1

Test #39:

score: 0

Accepted

time: 2ms

memory: 3376kb

input:

output:

result:

ok answer = 1

Test #40:

score: 0

Accepted

time: 10ms

memory: 3656kb

input:

output:

result:

ok answer = 1

Test #41:

score: 0

Accepted

time: 17ms

memory: 4048kb

input:

output:

result:

ok answer = 1

Test #42:

score: 0

Accepted

time: 12ms

memory: 3940kb

input:

output:

result:

ok answer = 1

Test #43:

score: 0

Accepted

time: 15ms

memory: 3944kb

input:

output:

result:

ok answer = 1

Test #44:

score: 0

Accepted

time: 7ms

memory: 3672kb

input:

output:

result:

ok answer = 1

Test #45:

score: 0

Accepted

time: 7ms

memory: 3412kb

input:

output:

result:

ok answer = 1

Test #46:

score: 0

Accepted

time: 7ms

memory: 3500kb

input:

output:

result:

ok answer = 1

Test #47:

score: 0

Accepted

time: 5ms

memory: 3396kb

input:

output:

result:

ok answer = 1

Test #48:

score: 0

Accepted

time: 15ms

memory: 4064kb

input:

output:

result:

ok answer = 1

Test #49:

score: 0

Accepted

time: 1ms

memory: 3416kb

input:

output:

result:

ok answer = 1

Test #50:

score: 0

Accepted

time: 8ms

memory: 4032kb

input:

output:

result:

ok answer = 1

Test #51:

score: 0

Accepted

time: 3ms

memory: 3556kb

input:

output:

result:

ok answer = 1

Test #52:

score: 0

Accepted

time: 12ms

memory: 4004kb

input:

output:

result:

ok answer = 1

Test #53:

score: 0

Accepted

time: 14ms

memory: 4028kb

input:

output:

result:

ok answer = 1

Test #54:

score: 0

Accepted

time: 9ms

memory: 3972kb

input:

output:

result:

ok answer = 1

Test #55:

score: 0

Accepted

time: 3ms

memory: 3392kb

input:

output:

result:

ok answer = 1

Test #56:

score: 0

Accepted

time: 5ms

memory: 3608kb

input:

output:

result:

ok answer = 1

Test #57:

score: 0

Accepted

time: 9ms

memory: 3524kb

input:

output:

result:

ok answer = 1

Test #58:

score: 0

Accepted

time: 12ms

memory: 3948kb

input:

output:

result:

ok answer = 1

Test #59:

score: 0

Accepted

time: 1ms

memory: 3404kb

input:

output:

result:

ok answer = 1

Test #60:

score: 0

Accepted

time: 2ms

memory: 3392kb

input:

output:

result:

ok answer = 1

Test #61:

score: 0

Accepted

time: 4ms

memory: 3604kb

input:

output:

result:

ok answer = 1

Test #62:

score: 0

Accepted

time: 7ms

memory: 3636kb

input:

output:

result:

ok answer = 1

Test #63:

score: 0

Accepted

time: 9ms

memory: 3604kb

input:

output:

result:

ok answer = 1

Test #64:

score: 0

Accepted

time: 6ms

memory: 3416kb

input:

output:

result:

ok answer = 1

Test #65:

score: 0

Accepted

time: 10ms

memory: 3528kb

input:

output:

result:

ok answer = 1

Test #66:

score: 0

Accepted

time: 11ms

memory: 3524kb

input:

output:

result:

ok answer = 1

Test #67:

score: 0

Accepted

time: 5ms

memory: 3480kb

input:

output:

result:

ok answer = 1

Test #68:

score: 0

Accepted

time: 7ms

memory: 3540kb

input:

output:

result:

ok answer = 1

Test #69:

score: 0

Accepted

time: 8ms

memory: 3924kb

input:

output:

result:

ok answer = 1

Test #70:

score: 0

Accepted

time: 11ms

memory: 3932kb

input:

output:

result:

ok answer = 1

Test #71:

score: 0

Accepted

time: 1ms

memory: 3460kb

input:

output:

result:

ok answer = 1