oj.uz

Submission #636041

# Submission time Handle Problem Language Result Execution time Memory
636041 2022-08-27T18:08:25 Z shafinalam Sorting (IOI15_sorting) C++14
100 / 100
 463 ms 27504 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 1 ms 340 KB Output is correct
4 Correct 0 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 1 ms 340 KB Output is correct
4 Correct 0 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.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 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 1 ms 340 KB Output is correct
4 Correct 0 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 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 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 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 2 ms 536 KB Output is correct
22 Correct 2 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 2 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 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 2 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 2 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 247 ms 16624 KB Output is correct
16 Correct 290 ms 24888 KB Output is correct
17 Correct 435 ms 26184 KB Output is correct
18 Correct 116 ms 22132 KB Output is correct
19 Correct 294 ms 24620 KB Output is correct
20 Correct 332 ms 25424 KB Output is correct
21 Correct 283 ms 25428 KB Output is correct
22 Correct 237 ms 21564 KB Output is correct
23 Correct 287 ms 27136 KB Output is correct
24 Correct 463 ms 27060 KB Output is correct
25 Correct 426 ms 26452 KB Output is correct
26 Correct 288 ms 25460 KB Output is correct
27 Correct 239 ms 24700 KB Output is correct
28 Correct 372 ms 26732 KB Output is correct
29 Correct 393 ms 25908 KB Output is correct
30 Correct 197 ms 24084 KB Output is correct
31 Correct 360 ms 26516 KB Output is correct
32 Correct 266 ms 26192 KB Output is correct
33 Correct 408 ms 26636 KB Output is correct
34 Correct 298 ms 26652 KB Output is correct
35 Correct 298 ms 24384 KB Output is correct
36 Correct 80 ms 22968 KB Output is correct
37 Correct 444 ms 27504 KB Output is correct
38 Correct 439 ms 26392 KB Output is correct
39 Correct 419 ms 26460 KB Output is correct