Submission #1088650

#TimeUsernameProblemLanguageResultExecution timeMemory
1088650vjudge1Xor Sort (eJOI20_xorsort)C++17
0 / 100
1103 ms207412 KiB
#include <bits/stdc++.h> using namespace std; #define fastinput cin.tie(nullptr)->sync_with_stdio(false); #define endl '\n' #define ll long long const ll mOd=1e9+7; const int mAx=INT_MAX; const int nUm=1e3+3; vector<int>a; int n,s; bool srtd(vector<int>b){ for(int i=0 ; i<b.size()-1 ; i++){ if((s==1 && b[i]>=b[i+1]) || (s==2 && b[i]>b[i+1])) return 0; } return 1; } vector<pair<int,int>>bfs(){ queue<pair<vector<int>,vector<pair<int,int>>>>q; map<vector<int>,bool>vis; q.push({a,{}}); vis[a]=1; while(!q.empty()){ auto [x,y]=q.front(); q.pop(); if(srtd(x)) return y; for(int i=0 ; i<x.size()-1 ; i++){ vector<int>v=x; v[i]=x[i]^x[i+1]; if(!vis[v]) { vis[v]=1; auto z=y; z.push_back({i,i+1}); q.push({v,z}); } v=x; v[i+1]=x[i]^x[i+1]; if(!vis[v]) { vis[v]=1; auto z=y; z.push_back({i+1,i}); q.push({v,z}); } } } return {}; } int main() { fastinput; cin>>n>>s; for(int i=0 ; i<n ; i++){ int x; cin>>x; a.push_back(x); } vector<pair<int,int>>v=bfs(); cout<<v.size()<<endl; for(auto it:v)cout<<it.first+1<<" "<<it.second+1<<endl; }

Compilation message (stderr)

xorsort.cpp: In function 'bool srtd(std::vector<int>)':
xorsort.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0 ; i<b.size()-1 ; i++){
      |                   ~^~~~~~~~~~~
xorsort.cpp: In function 'std::vector<std::pair<int, int> > bfs()':
xorsort.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i=0 ; i<x.size()-1 ; i++){
      |                       ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...