oj.uz

Submission #387364

# Submission time Handle Problem Language Result Execution time Memory
387364 2021-04-08T09:59:32 Z mehrdad_sohrabi Sorting (IOI15_sorting) C++14
74 / 100
 328 ms 20980 KB 
/// 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=2e5+100;
ll par[N];
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

sorting.cpp: In function 'll check(ll, int32_t, int32_t*, int32_t, int32_t*, int32_t*)':
sorting.cpp:65: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]
   65 |     if (cng.size()>tool) return 0;
      |         ~~~~~~~~~~^~~~~
sorting.cpp:70:13: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   70 |         pii p=cng.back();
      |             ^
sorting.cpp:23:48: warning: unused parameter 'm' [-Wunused-parameter]
   23 | ll check(ll tool,int32_t n,int32_t s[],int32_t m,int32_t x[],int32_t y[]){
      |                                        ~~~~~~~~^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1132 KB Output is correct
17 Correct 2 ms 1132 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 3 ms 1388 KB Output is correct
22 Correct 3 ms 1388 KB Output is correct
23 Correct 3 ms 1388 KB Output is correct
24 Correct 3 ms 1388 KB Output is correct
25 Correct 3 ms 1388 KB Output is correct
26 Correct 3 ms 1408 KB Output is correct
27 Correct 3 ms 1388 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1260 KB Output is correct
2 Correct 4 ms 1388 KB Output is correct
3 Correct 4 ms 1388 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 3 ms 1404 KB Output is correct
8 Correct 5 ms 1388 KB Output is correct
9 Correct 4 ms 1388 KB Output is correct
10 Correct 3 ms 1388 KB Output is correct
11 Correct 4 ms 1388 KB Output is correct
12 Correct 3 ms 1388 KB Output is correct
13 Correct 4 ms 1388 KB Output is correct
14 Correct 3 ms 1260 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1260 KB Output is correct
2 Correct 4 ms 1388 KB Output is correct
3 Correct 4 ms 1388 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1260 KB Output is correct
7 Correct 3 ms 1404 KB Output is correct
8 Correct 5 ms 1388 KB Output is correct
9 Correct 4 ms 1388 KB Output is correct
10 Correct 3 ms 1388 KB Output is correct
11 Correct 4 ms 1388 KB Output is correct
12 Correct 3 ms 1388 KB Output is correct
13 Correct 4 ms 1388 KB Output is correct
14 Correct 3 ms 1260 KB Output is correct
15 Correct 262 ms 19944 KB Output is correct
16 Correct 295 ms 20588 KB Output is correct
17 Correct 328 ms 20980 KB Output is correct
18 Correct 45 ms 13036 KB Output is correct
19 Incorrect 209 ms 20836 KB Output isn't correct
20 Halted 0 ms 0 KB -