Submission #387367

#	Time	Username	Problem	Language	Result	Execution time	Memory
387367		mehrdad_sohrabi	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KiB

sorting

/// Black lives matter
#include <bits/stdc++.h>
#include "sorting.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=6e5+100;
ll W[N];
ll koj[N];
ll ans1[N],ans2[N];
ll check(ll tool,int32_t n,int32_t s[],int32_t m,int32_t x[],int32_t y[]){
    for (int i=0;i<N;i++) par[i]=i;
    for (int i=0;i<n;i++) W[i]=s[i];
    for (int i=0;i<tool;i++){
        swap(W[x[i]],W[y[i]]);
    }
    for (int i=0;i<n;i++){
        koj[W[i]]=i;
    }
    vector <pii> cng;
    for (int i=0;i<n;i++){
        if (koj[i]!=i){
            cng.pb({W[i],i});
          //  if (tool==3) cout <<  W[i] << " tool " << i << endl;
            swap(W[koj[i]],W[i]);
            ll z=koj[i];
            koj[i]=i;
            koj[W[z]]=z;
        }
    }
    for (int i=0;i<n;i++){
        W[i]=s[i];
    }
    for (int i=0;i<tool;i++){
        swap(W[x[i]],W[y[i]]);
    }
    for (int i=0;i<n;i++){
        koj[W[i]]=i;
    }
    /*
    if (tool==3){
        for (int i=0;i<n;i++){
            cout << W[i] << " W ";
        }
        cout << endl;
        for (int i=0;i<n;i++){
            cout << koj[i] << " koj ";
        }
        cout << endl;
    }
    */
 //   cout << cng.size() << " " << tool << endl;
    if (cng.size()>tool) return 0;
    reverse(cng.begin(),cng.end());
    for (int i=tool-1;i>-1;i--){
        ans1[i]=koj[cng.back().F];
        ans2[i]=koj[cng.back().S];
        pii p=cng.back();
        cng.pop_back();
        swap(W[x[i]],W[y[i]]);
        swap(koj[W[x[i]]],koj[W[y[i]]]);
        if (ans1[i]>ans2[i]) swap(ans1[i],ans2[i]);
        if (cng.size()==0) break;
    }
    return 1;
}
int32_t findSwapPairs(int32_t n, int32_t s[], int32_t m, int32_t x[], int32_t y[], int32_t p[], int32_t q[]) {
    /// yadet nare W=s koni
    ll p1=0;
    for (int i=1;i<n;i++) if (s[i]<s[i-1]) p1=1;
    if (p1==0) return 0;
    ll l=0,r=m;
    while(r-l>1){
      //  cout << l << " " << r << endl;
        ll mid=(r+l)/2;
        if (check(mid,n,s,m,x,y)) r=mid;
        else l=mid;
    }
    ll ans=r;
    check(r,n,s,m,x,y);
    for (int i=0;i<ans;i++){
        p[i]=ans1[i];
        q[i]=ans2[i];
    }
    return ans;
}
/*
int32_t s[N],x[N],y[N],p[N],q[N];
int32_t main(){
    ll n,m;
    cin >> n;
    for (int i=0;i<n;i++) cin >> s[i];
    cin >> m;
    for (int i=0;i<m;i++) cin >> x[i] >> y[i];
    ll ans=findSwapPairs(n,s,m,x,y,p,q);
    cout << ans << " ans " << endl;;
    for (int i=0;i<ans;i++){
        cout << ans1[i] << " " << ans2[i] << endl;
    }
}
*/
/*
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4

*/

Compilation message (stderr)

sorting.cpp: In function 'll check(ll, int32_t, int32_t*, int32_t, int32_t*, int32_t*)':
sorting.cpp:23:27: error: 'par' was not declared in this scope
   23 |     for (int i=0;i<N;i++) par[i]=i;
      |                           ^~~
sorting.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   64 |     if (cng.size()>tool) return 0;
      |         ~~~~~~~~~~^~~~~
sorting.cpp:22:48: warning: unused parameter 'm' [-Wunused-parameter]
   22 | ll check(ll tool,int32_t n,int32_t s[],int32_t m,int32_t x[],int32_t y[]){
      |                                        ~~~~~~~~^