fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. namespace __gnu_pbds{typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;}
  10. using namespace __gnu_pbds;
  11.  
  12. void init()
  13. {
  14.     cin.tie(0);
  15.     cin.sync_with_stdio(0);
  16.     cout.tie(0);
  17. }
  18.  
  19. bool preceed(pair<ll,ll> a,pair<ll,ll> b)
  20. {
  21.     return a.second<b.second;
  22. }
  23.  
  24.  
  25. void solution(int test)
  26. {
  27.     int n; cin>>n;
  28.     int a[n],b[n];
  29.     map<int,set<int>> mp;
  30.     for(int i=0; i<n; i++)
  31.     {
  32.         cin>>a[i];
  33.         b[i] = a[i];
  34.         mp[a[i]].insert(i);
  35.     }
  36.     sort(b,b+n);
  37.  
  38.     for(int i=0; i<n; i++)
  39.     {
  40.         if(a[i]!=b[i])
  41.         {
  42.             int ink = -1;
  43.             for(auto it:mp[b[i]])
  44.             {
  45.                 if(abs(i-it)%2==0)
  46.                 {
  47.                     swap(a[i],a[it]);
  48.                     ink = it;
  49.                     break;
  50.                 }
  51.             }
  52.             if(ink==-1)
  53.             {
  54.                 cout<<"NO\n"; return;
  55.             }else
  56.             {
  57.                 mp[b[i]].erase(ink);
  58.                 mp[a[i]].insert(ink);
  59.                 mp[a[i]].erase(i);
  60.             }
  61.         }else
  62.         {
  63.             mp[a[i]].erase(i);
  64.         }
  65.     }
  66.  
  67.     cout<<"YES\n";
  68.  
  69. }
  70.  
  71. int main()
  72. {
  73.    //freopen("erase.in","r",stdin);
  74.     //freopen("output.out","w",stdout);
  75.  
  76.     init();
  77.  
  78.     int t=1,test=1;
  79.  
  80.     //cin>>t;
  81.  
  82.     while(t--)
  83.     {
  84.         solution(test++);
  85.     }
  86.  
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
5
1 3 4 1 2
stdout
copy 
YES
https://ideone.com/HmGE7T
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!