oj.uz

Submission #387366

# Submission time Handle Problem Language Result Execution time Memory
387366 2021-04-08T10:01:15 Z mehrdad_sohrabi Sorting (IOI15_sorting) C++14
74 / 100
 346 ms 27116 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=6e5+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 2 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 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 2 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 4 ms 2796 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 3 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2668 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 2 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 4 ms 2796 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 3 ms 2796 KB Output is correct
17 Correct 3 ms 2796 KB Output is correct
18 Correct 3 ms 2668 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 5 ms 2796 KB Output is correct
22 Correct 4 ms 2924 KB Output is correct
23 Correct 5 ms 2924 KB Output is correct
24 Correct 5 ms 2928 KB Output is correct
25 Correct 4 ms 2924 KB Output is correct
26 Correct 4 ms 2924 KB Output is correct
27 Correct 5 ms 2924 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2796 KB Output is correct
2 Correct 5 ms 2796 KB Output is correct
3 Correct 5 ms 2796 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 2796 KB Output is correct
6 Correct 4 ms 2796 KB Output is correct
7 Correct 5 ms 2796 KB Output is correct
8 Correct 5 ms 2796 KB Output is correct
9 Correct 5 ms 2924 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2796 KB Output is correct
12 Correct 4 ms 2796 KB Output is correct
13 Correct 6 ms 3072 KB Output is correct
14 Correct 4 ms 2796 KB Output is correct
15 Correct 257 ms 14800 KB Output is correct
16 Correct 290 ms 14956 KB Output is correct
17 Correct 328 ms 16248 KB Output is correct
18 Correct 41 ms 5868 KB Output is correct
19 Correct 210 ms 16100 KB Output is correct
20 Correct 224 ms 23340 KB Output is correct
21 Correct 217 ms 23720 KB Output is correct
22 Correct 265 ms 19452 KB Output is correct
23 Correct 292 ms 23700 KB Output is correct
24 Correct 328 ms 23888 KB Output is correct
25 Correct 338 ms 23996 KB Output is correct
26 Correct 236 ms 20668 KB Output is correct
27 Correct 211 ms 20616 KB Output is correct
28 Correct 312 ms 23292 KB Output is correct
29 Correct 317 ms 23172 KB Output is correct
30 Correct 163 ms 19568 KB Output is correct
31 Correct 346 ms 22948 KB Output is correct
32 Correct 285 ms 23724 KB Output is correct
33 Correct 336 ms 23884 KB Output is correct
34 Correct 305 ms 24104 KB Output is correct
35 Correct 218 ms 23700 KB Output is correct
36 Runtime error 83 ms 27116 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -