oj.uz

Submission #137427

# Submission time Handle Problem Language Result Execution time Memory
137427 2019-07-27T17:52:29 Z Runtime_error_ Sorting (IOI15_sorting) C++14
100 / 100
 693 ms 28280 KB 
//100 points
#include "sorting.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 6e5+9;
int n,m,x[inf],y[inf],a[inf],pos[inf],from[inf],origin[inf],posfrom[inf];

bool check(int i,int p[],int q[]){

        int l = 0,notvalid = 0;
        for(int j=0;j<n;j++){
            from[j] = j;
            a[j] = origin[j];
            p[j] = q[j] = 0;
            pos[ a[j] ] = j;
            posfrom[ from[j] ] = j;
            notvalid += (a[j] != j);
        }
        //cout<<i<<" "<<notvalid<<endl;
         for(int j=i;j>=0;j--){
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
            swap( from[ x[j] ] , from[ y[j] ] );
        }

        for(int j=0;j<=i;j++){

            swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);

            notvalid -= (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(a[ x[j] ] , a[ y[j] ] );
            notvalid += (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(from[ x[j] ] , from[ y[j] ]);

            //cout<<notvalid<<" ";
            int idx,idfrom;

            while(l<n){
                idx = pos[l];
                idfrom = posfrom[l];
                if(idx != idfrom)
                    break;
                l++;
            }
            swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
            notvalid -= (a[idx] != idx) + (a[idfrom] != idfrom);
            swap(a[idx],a[idfrom]);
            notvalid += (a[idx] != idx) + (a[idfrom] != idfrom);

            //cout<<notvalid<<" ";
            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            //cout<<"swap "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
            if(notvalid == 0)
                return 1;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        return 0;
}

int findSwapPairs(int N, int A[], int M, int X[], int Y[], int p[], int q[]){
    n = N;
    m = M;
    bool tr = 1;
    for(int i=0;i<n;i++){
        a[i] = A[i];
        pos[ a[i] ] = i;
        origin[i] = a[i];
        if(a[i] != i)
            tr = 0;
    }
    if(tr)
        return 0;

    for(int i=0;i<m;i++)
        x[i] = X[i],y[i] = Y[i];

    int l = 0 , r = m-1;
    while(r-l>1){
        if(check(mid,p,q))
            r = mid;
        else
            l = mid;
    }
    if(check(0,p,q))
        r = 0;
    check(r,p,q);
    return r+1;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 276 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 380 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 276 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 760 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 4 ms 764 KB Output is correct
24 Correct 4 ms 808 KB Output is correct
25 Correct 4 ms 760 KB Output is correct
26 Correct 3 ms 764 KB Output is correct
27 Correct 4 ms 760 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 4 ms 636 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 359 ms 24180 KB Output is correct
16 Correct 496 ms 25444 KB Output is correct
17 Correct 693 ms 26860 KB Output is correct
18 Correct 47 ms 15612 KB Output is correct
19 Correct 334 ms 26360 KB Output is correct
20 Correct 364 ms 27000 KB Output is correct
21 Correct 356 ms 26972 KB Output is correct
22 Correct 369 ms 21624 KB Output is correct
23 Correct 410 ms 27896 KB Output is correct
24 Correct 643 ms 27388 KB Output is correct
25 Correct 652 ms 27160 KB Output is correct
26 Correct 449 ms 27000 KB Output is correct
27 Correct 418 ms 26232 KB Output is correct
28 Correct 598 ms 27384 KB Output is correct
29 Correct 601 ms 27000 KB Output is correct
30 Correct 323 ms 25848 KB Output is correct
31 Correct 593 ms 27516 KB Output is correct
32 Correct 435 ms 26564 KB Output is correct
33 Correct 662 ms 27648 KB Output is correct
34 Correct 558 ms 27452 KB Output is correct
35 Correct 339 ms 25848 KB Output is correct
36 Correct 90 ms 24568 KB Output is correct
37 Correct 556 ms 28280 KB Output is correct
38 Correct 539 ms 27128 KB Output is correct
39 Correct 554 ms 27360 KB Output is correct