oj.uz

Submission #624161

# Submission time Handle Problem Language Result Execution time Memory
624161 2022-08-07T11:00:25 Z mdn2002 Sorting (IOI15_sorting) C++14
100 / 100
 457 ms 18576 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;

int n , m , a [200005] , aa [200005] , x [600005] , y [600005] , dis [200005] , wrdis [200005] , wra [200005] , P [600005] , Q [600005];


bool ck ( int xx )
{
    for ( int i = 1 ; i <= n ; i ++ )
    {
        a [i] = aa [i];
        wra [ a [i] ] = i;
    }
    int mm = xx;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        dis [i] = i;
        wrdis [ dis [i] ] = i;
    }
    for ( int j = mm - 1 ; j >= 0 ; j -- )
    {
        swap ( dis [ x [j] ] , dis [ y [j] ] );
        swap ( wrdis [ dis [ x [j] ] ] , wrdis [ dis [ y [j] ] ] );
    }
    deque < int > s;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( dis [i] != a [i] ) s . push_back ( dis [i] );
    }

    for ( int i = 1 ; i <= mm ; i ++ )
    {

        swap ( a [ x [ i - 1 ] ] , a [ y [ i - 1 ] ] );
        swap ( wra [ a [ x [ i - 1 ] ] ] , wra [ a [ y [ i - 1 ] ] ] );
        swap ( dis [ x [ i - 1 ] ] , dis [ y [ i - 1 ] ] );
        swap ( wrdis [ dis [ x [ i - 1 ] ] ] , wrdis [ dis [ y [ i - 1 ] ] ] );

        while ( s . size () )
        {

            int x = * s . begin () , z = wra [x];
            s . pop_front ();
            if ( dis [ wrdis [x] ] == a [ wrdis [x] ] ) continue;

            swap ( a [ wrdis [x] ] , a [z] );
            swap ( wra [ a [ wrdis [x] ] ] , wra [ a [z] ] );
            break;

        }
    }
    int f = 0;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( a [i] != i ) f = 1;
    }
    if ( f == 0 ) return 1;
    return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

    n = N;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        a [i] = S [ i - 1 ];
        a [i] ++;
        aa [i] = a [i];
    }
    m = M;
    for ( int i = 0 ; i < m ; i ++ )
    {
        x [i] = X [i] , y [i] = Y [i];
        x [i] ++ , y [i] ++;
    }

    int l = 0 , rr = m + 1 , mid;
    while ( l < rr )
    {
        mid = ( l + rr ) / 2;
        if ( ck ( mid ) ) rr = mid;
        else l = mid + 1;
    }
    m = l;

    for ( int i = 1 ; i <= n ; i ++ )
    {
        a [i] = aa [i];
        wra [ a [i] ] = i;
    }
    for ( int i = 1 ; i <= n ; i ++ )
    {
        dis [i] = i;
        wrdis [i] = i;
    }
    for ( int j = m - 1 ; j >= 0 ; j -- )
    {
        swap ( dis [ x [j] ] , dis [ y [j] ] );
        swap ( wrdis [ dis [ x [j] ] ] , wrdis [ dis [ y [j] ] ] );
    }

    deque < int > s;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        if ( dis [i] != a [i] ) s . push_back ( dis [i] );
    }

    int r = 0;
    for ( int i = 1 ; i <= m ; i ++ )
    {

        swap ( a [ x [ i - 1 ] ] , a [ y [ i - 1 ] ] );
        swap ( wra [ a [ x [ i - 1 ] ] ] , wra [ a [ y [ i - 1 ] ] ] );
        swap ( dis [ x [ i - 1 ] ] , dis [ y [ i - 1 ] ] );
        swap ( wrdis [ dis [ x [ i - 1 ] ] ] , wrdis [ dis [ y [ i - 1 ] ] ] );



        P [ i - 1 ] = -1 , Q [ i - 1 ] = -1;
        while ( s . size () )
        {

            int x = * s . begin () , z = wra [x];
            s . pop_front ();
            if ( dis [ wrdis [x] ] == a [ wrdis [x] ] ) continue;

            swap ( a [ wrdis [x] ] , a [z] );
            swap ( wra [ a [ wrdis [x] ] ] , wra [ a [z] ] );

            P [ i - 1 ] = wrdis [x] - 1 , Q [ i - 1 ] = z - 1;
            r ++;
            break;

        }

        if ( P [ i - 1 ] == -1 )
        {
            P [ i - 1 ] = 0;
            Q [ i - 1 ] = 0;
            r ++;
        }

    }
    return r;
}

Compilation message

sorting.cpp: In function 'bool ck(int)':
sorting.cpp:43:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   43 |             int x = * s . begin () , z = wra [x];
      |                 ^
sorting.cpp:5:40: note: shadowed declaration is here
    5 | int n , m , a [200005] , aa [200005] , x [600005] , y [600005] , dis [200005] , wrdis [200005] , wra [200005] , P [600005] , Q [600005];
      |                                        ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:73: warning: declaration of 'Q' shadows a global declaration [-Wshadow]
   61 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                                                     ~~~~^~~
sorting.cpp:5:126: note: shadowed declaration is here
    5 | int n , m , a [200005] , aa [200005] , x [600005] , y [600005] , dis [200005] , wrdis [200005] , wra [200005] , P [600005] , Q [600005];
      |                                                                                                                              ^
sorting.cpp:61:64: warning: declaration of 'P' shadows a global declaration [-Wshadow]
   61 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                                            ~~~~^~~
sorting.cpp:5:113: note: shadowed declaration is here
    5 | int n , m , a [200005] , aa [200005] , x [600005] , y [600005] , dis [200005] , wrdis [200005] , wra [200005] , P [600005] , Q [600005];
      |                                                                                                                 ^
sorting.cpp:123:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  123 |             int x = * s . begin () , z = wra [x];
      |                 ^
sorting.cpp:5:40: note: shadowed declaration is here
    5 | int n , m , a [200005] , aa [200005] , x [600005] , y [600005] , dis [200005] , wrdis [200005] , wra [200005] , P [600005] , Q [600005];
      |                                        ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 255 ms 16552 KB Output is correct
16 Correct 288 ms 17004 KB Output is correct
17 Correct 386 ms 17788 KB Output is correct
18 Correct 109 ms 14028 KB Output is correct
19 Correct 316 ms 16084 KB Output is correct
20 Correct 302 ms 16516 KB Output is correct
21 Correct 307 ms 16640 KB Output is correct
22 Correct 253 ms 18128 KB Output is correct
23 Correct 299 ms 18492 KB Output is correct
24 Correct 428 ms 18208 KB Output is correct
25 Correct 454 ms 17848 KB Output is correct
26 Correct 241 ms 16548 KB Output is correct
27 Correct 243 ms 16024 KB Output is correct
28 Correct 371 ms 18072 KB Output is correct
29 Correct 348 ms 17412 KB Output is correct
30 Correct 207 ms 15340 KB Output is correct
31 Correct 383 ms 17828 KB Output is correct
32 Correct 289 ms 17908 KB Output is correct
33 Correct 446 ms 18116 KB Output is correct
34 Correct 352 ms 18136 KB Output is correct
35 Correct 353 ms 15860 KB Output is correct
36 Correct 78 ms 14216 KB Output is correct
37 Correct 457 ms 18576 KB Output is correct
38 Correct 446 ms 18040 KB Output is correct
39 Correct 441 ms 18020 KB Output is correct