QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82032#5575. Knight's Tour ReduxRUET_phoenix#WA 1ms3292kbC++202.1kb2023-02-26 23:04:312023-02-26 23:04:37

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 23:04:37]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3292kb
  • [2023-02-26 23:04:31]
  • Submitted

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)