oj.uz

Submission #65066

# Submission time Handle Problem Language Result Execution time Memory
65066 2018-08-06T14:09:11 Z Bodo171 Sorting (IOI15_sorting) C++14
100 / 100
 582 ms 19488 KB 
#include "sorting.h"
#include <iostream>
const int nmax=200005;
using namespace std;
int i,n,idx,u;
int en[nmax],v[nmax],p[nmax],poz[nmax],a[3*nmax],b[3*nmax],A[3*nmax],B[3*nmax];
bool check(int val)
{
     for(i=0;i<n;i++)
        poz[v[i]]=i,p[i]=v[i];
     for(i=0;i<val;i++)
        swap(v[a[i]],v[b[i]]);
     for(i=0;i<n;i++)
        en[v[i]]=i;//en[i]-pozitia pe care ajunge elementul i;
    idx=0;u=0;
    for(i=0;i<val;i++)
    {
        swap(p[a[i]],p[b[i]]);
        swap(poz[p[a[i]]],poz[p[b[i]]]);
        while(idx<n&&en[idx]==idx) idx++;
        if(idx<n)
        {
            en[v[idx]]=en[idx];//acum elementul care era pe pozitia noastra ajunge unde ar fi ajuns al noostru
            v[en[idx]]=v[idx];//facem asta si la nivelul sirului
            A[u]=poz[idx];B[u]=poz[v[idx]];
            ++u;
            swap(poz[idx],poz[v[idx]]);
            swap(p[poz[idx]],p[poz[v[idx]]]);
            idx++;
        }
    }
    while(idx<n&&en[idx]==idx) idx++;
    return (idx==n);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int ans=M;
    n=N;
    for(i=0;i<M;i++)
        a[i]=X[i],b[i]=Y[i];
    for(int p=19;p>=0;p--)
    {
        for(i=0;i<N;i++)
          v[i]=S[i];
        if(ans-(1<<p)>=0&&check(ans-(1<<p)))
            ans-=(1<<p);
    }
    for(i=0;i<N;i++)
          v[i]=S[i];
    int okceva=check(ans);
    for(i=0;i<u;i++)
        P[i]=A[i],Q[i]=B[i];
    for(i=u;i<ans;i++)
        P[i]=Q[i]=0;
	return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:40:13: warning: declaration of 'p' shadows a global declaration [-Wshadow]
     for(int p=19;p>=0;p--)
             ^
sorting.cpp:6:22: note: shadowed declaration is here
 int en[nmax],v[nmax],p[nmax],poz[nmax],a[3*nmax],b[3*nmax],A[3*nmax],B[3*nmax];
                      ^
sorting.cpp:52:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=u;i<ans;i++)
     ^~~
sorting.cpp:54:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return ans;
  ^~~~~~
sorting.cpp:49:9: warning: unused variable 'okceva' [-Wunused-variable]
     int okceva=check(ans);
         ^~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 499 ms 17196 KB Output is correct
16 Correct 404 ms 17584 KB Output is correct
17 Correct 433 ms 18400 KB Output is correct
18 Correct 64 ms 12920 KB Output is correct
19 Correct 292 ms 16764 KB Output is correct
20 Correct 325 ms 17200 KB Output is correct
21 Correct 336 ms 17400 KB Output is correct
22 Correct 472 ms 18812 KB Output is correct
23 Correct 433 ms 19220 KB Output is correct
24 Correct 435 ms 19104 KB Output is correct
25 Correct 449 ms 18680 KB Output is correct
26 Correct 406 ms 16632 KB Output is correct
27 Correct 374 ms 15804 KB Output is correct
28 Correct 441 ms 18576 KB Output is correct
29 Correct 398 ms 17980 KB Output is correct
30 Correct 249 ms 15000 KB Output is correct
31 Correct 399 ms 18436 KB Output is correct
32 Correct 463 ms 18552 KB Output is correct
33 Correct 582 ms 18816 KB Output is correct
34 Correct 489 ms 18912 KB Output is correct
35 Correct 233 ms 16452 KB Output is correct
36 Correct 55 ms 13560 KB Output is correct
37 Correct 396 ms 19488 KB Output is correct
38 Correct 416 ms 18780 KB Output is correct
39 Correct 436 ms 18936 KB Output is correct