QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#82032 | #5575. Knight's Tour Redux | RUET_phoenix# | WA | 1ms | 3292kb | C++20 | 2.1kb | 2023-02-26 23:04:31 | 2023-02-26 23:04:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
int main() {
int n ;
cin>>n ;
if( (n-1) % 4 == 0 and n > 5)
{
ll x =n / 4 ;
vector<pair <ll,ll>>ans ;
ll j , i ;
ans.pb({1,1}) ;
for (i = 0 ; i < x ; i++) ans.pb({ans.back().first + 1 , ans.back().second + 3}) ;
for (i = 0 ; i < x ; i++) ans.pb({ans.back().first + 3 , ans.back().second + 1}) ;
x = ans.size() ;
for (i = x - 1 ; i>0 ; i--) ans.pb({ ans[i].second , ans[i].first }) ;
map<ll,ll>mp1 , mp2 ;
for (auto it : ans) {
if (mp1[it.first]) {
cout<<"IMPOSSIBLE\n" ;
return 0 ;
}
if(mp2[it.second]) {
cout<<"IMPOSSIBLE\n" ;
return 0 ;
}
mp1[it.first] ++ ;
mp2[it.second] ++ ;
}
cout<<"POSSIBLE\n" ;
for (auto it : ans) cout << it.first << ' ' << it.second << '\n' ;
}
else if ((n - 2) % 4 == 0 and n > 5) {
ll x =(n - 2) / 4 ;
vector<pair <ll,ll>>ans ;
ll j , i ;
ans.pb({1,1}) ;
ll id = -1 ;
for (i = 0 ; i < x ; i++) { ans.pb({ans.back().first + 1 , ans.back().second + 3}) ; }
for (i = 0 ; i < x ; i++) { ans.pb({ans.back().first + 3 , ans.back().second + id}) ; id *= -1 ;}
x = ans.size() ;
ans.pb({n,n}) ;
for (i = x - 1 ; i>0 ; i--) ans.pb({ans[i].second , ans[i].first }) ;
map<ll,ll>mp1 , mp2 ;
for (auto it : ans) {
if (mp1[it.first]) {
cout<<"IMPOSSIBLE\n" ;
return 0 ;
}
if(mp2[it.second]) {
cout<<"IMPOSSIBLE\n" ;
return 0 ;
}
mp1[it.first] ++ ;
mp2[it.second] ++ ;
}
cout<<"POSSIBLE\n" ;
for (auto it : ans) cout << it.first << ' ' << it.second << '\n' ;
}
else
{
cout<<"IMPOSSIBLE\n" ;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3292kb
input:
1
output:
IMPOSSIBLE
result:
wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)