oj.uz

Submission #874584

# Submission time Handle Problem Language Result Execution time Memory
874584 2023-11-17T10:49:00 Z HuyQuang_re_Zero Sorting (IOI15_sorting) C++14
100 / 100
 148 ms 39732 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "sorting.h"
#define mxn 600005
using namespace std;
int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
bool check(int k)
{
    for(i=1;i<=n;i++) tg[i]=p[i],r[i]=i;
    int comp=n;
    for(i=1;i<=k;i++) swap(p[x[i]],p[y[i]]);
    for(i=1;i<=n;i++)
        if(root(i)!=root(p[i]))
        {
            r[root(i)]=root(p[i]);
            comp--;
        }
    for(i=1;i<=n;i++) p[i]=tg[i];
    return n-comp<=k;
}
int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
{
    n=_n;
    for(i=n;i>=1;i--) p[i]=_p[i-1],p[i]++;
    m=_m;
    for(i=m;i>=1;i--) x[i]=_x[i-1],y[i]=_y[i-1],x[i]++,y[i]++;
    int l=0,r=m;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid; else l=mid+1;
    }

    /////////////////////////////////////////////////////////////////////////////
    for(i=1;i<=n;i++) tg[i]=p[i];
    vector <II> vec;
    for(i=1;i<=l;i++) swap(p[x[i]],p[y[i]]);
    for(i=1;i<=n;i++)
        if(visited[i]==0)
        {
            int u=i;
            while(p[u]!=i)
            {
                //cerr<<u-1<<" "<<p[u]-1<<'\n';
                vec.push_back({ u,p[u] }),u=p[u],visited[u]=1;
            }
            visited[u]=1;
        }
    for(i=1;i<=n;i++) vec.push_back({ i,i });
    reverse(vec.begin(),vec.end());
    for(i=1;i<=n;i++) p[i]=tg[i];
    //////////////////////////////////////////////////////////////////////////////////

    cerr<<'\n';
    for(i=1;i<=n;i++) pos[p[i]]=i;
    int res=0;
    for(i=1;i<=l;i++)
    {
        swap(pos[p[x[i]]],pos[p[y[i]]]);
        swap(p[x[i]],p[y[i]]);
        /*
        cout<<x[i]-1<<" "<<y[i]-1<<'\n';
        for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
        cout<<'\n';
        */
        int u=pos[vec.back().fst],v=pos[vec.back().snd]; vec.pop_back();
        swap(pos[p[u]],pos[p[v]]);
        swap(p[u],p[v]);
        /*
        cout<<u-1<<" "<<v-1<<'\n';
        for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
        cout<<'\n';*/
        a[res]=u-1; b[res]=v-1;
        res++;
    }
    return res;
}
/*
int main()
{
    freopen("sorting.inp","r",stdin);
    freopen("sorting.out","w",stdout);
    cin>>n;
    for(i=0;i<n;i++) cin>>p[i];
    cin>>m;
    for(i=0;i<m;i++) cin>>x[i]>>y[i];
    cout<<(res=findSwapPairs(n,p,m,x,y,a,b))<<'\n';
    for(i=0;i<res;i++) cout<<a[i]<<" "<<b[i]<<'\n';
}
*/

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:72: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                                    ~~~~^~~
sorting.cpp:19:80: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                                ^
sorting.cpp:35:64: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   35 | int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
      |                                                            ~~~~^~~
sorting.cpp:19:73: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                         ^
sorting.cpp:41:13: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   41 |     int l=0,r=m;
      |             ^
sorting.cpp:19:33: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                 ^
sorting.cpp:70:9: warning: declaration of 'res' shadows a global declaration [-Wshadow]
   70 |     int res=0;
      |         ^~~
sorting.cpp:19:69: note: shadowed declaration is here
   19 | int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
      |                                                                     ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12680 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 1 ms 12736 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12788 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12680 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 2 ms 12636 KB Output is correct
18 Correct 1 ms 12736 KB Output is correct
19 Correct 2 ms 12636 KB Output is correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 2 ms 12972 KB Output is correct
22 Correct 2 ms 12892 KB Output is correct
23 Correct 2 ms 12892 KB Output is correct
24 Correct 2 ms 12904 KB Output is correct
25 Correct 2 ms 12904 KB Output is correct
26 Correct 2 ms 12892 KB Output is correct
27 Correct 2 ms 12892 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12860 KB Output is correct
5 Correct 3 ms 13256 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12860 KB Output is correct
5 Correct 3 ms 13256 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 112 ms 36560 KB Output is correct
16 Correct 122 ms 36880 KB Output is correct
17 Correct 138 ms 37440 KB Output is correct
18 Correct 64 ms 31688 KB Output is correct
19 Correct 119 ms 39428 KB Output is correct
20 Correct 123 ms 39104 KB Output is correct
21 Correct 124 ms 39404 KB Output is correct
22 Correct 109 ms 32920 KB Output is correct
23 Correct 143 ms 39100 KB Output is correct
24 Correct 134 ms 38788 KB Output is correct
25 Correct 148 ms 38540 KB Output is correct
26 Correct 129 ms 39732 KB Output is correct
27 Correct 129 ms 36032 KB Output is correct
28 Correct 148 ms 39032 KB Output is correct
29 Correct 128 ms 38920 KB Output is correct
30 Correct 99 ms 34756 KB Output is correct
31 Correct 130 ms 38500 KB Output is correct
32 Correct 132 ms 38068 KB Output is correct
33 Correct 147 ms 38732 KB Output is correct
34 Correct 132 ms 38804 KB Output is correct
35 Correct 120 ms 39020 KB Output is correct
36 Correct 54 ms 35268 KB Output is correct
37 Correct 137 ms 39360 KB Output is correct
38 Correct 130 ms 38348 KB Output is correct
39 Correct 139 ms 39716 KB Output is correct