QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #82035 | #5575. Knight's Tour Redux | RUET_phoenix# | WA | 1ms | 3392kb | C++20 | 2.2kb | 2023-02-26 23:05:39 | 2023-02-26 23:06:28 |
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 >= 2 and n <=5)
{
cout<<"IMPOSSIBLE\n" ;
}
else if( (n-1) % 4 == 0 )
{
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 ) {
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: 100
Accepted
time: 1ms
memory: 3256kb
input:
1
output:
POSSIBLE 1 1
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
2
output:
IMPOSSIBLE
result:
ok answer = 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3280kb
input:
3
output:
IMPOSSIBLE
result:
ok answer = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
4
output:
IMPOSSIBLE
result:
ok answer = 0
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3252kb
input:
5
output:
IMPOSSIBLE
result:
wrong answer jury has the better answer: jans = 1, pans = 0 (1 is Possible)