oj.uz

Submission #134311

# Submission time Handle Problem Language Result Execution time Memory
134311 2019-07-22T12:05:42 Z Runtime_error_ Sorting (IOI15_sorting) C++14
20 / 100
 1000 ms 376 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e3+9;
int pos[inf],from[inf],origin[inf];

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[]){

    bool tr = 1;
    for(int i=0;i<n;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++){
        int l = 0;
        for(int j=0;j<n;j++)
            from[j] = j,a[j] = origin[j],p[j] = q[j] = 0;
         for(int j=i;j>=0;j--)
            swap( from[ x[j] ] , from[ y[j] ] );

        /*for(int j=0;j<n;j++)
            cout<<from[j]<<" ";
        cout<<endl;*/

        for(int j=0;j<=i;j++){
            swap(a[ x[j] ] , a[ y[j] ] );
            swap(from[ x[j] ] , from[ y[j] ]);
            int idx,idfrom;

            while(l<n){
                for(idx = 0;idx<n && a[idx] != l;idx++);
                for(idfrom = 0;idfrom<n && from[idfrom] != l;idfrom++);
                if(from[idx] != idfrom)
                    break;
                l++;
            }
            swap(a[idx],a[idfrom]);
            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        tr = 1;
        for(int i=0;i<n;i++)
            if(a[i] != i)
                tr = 0;
        if(tr)
            return i+1;
    }
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:50:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i=0;i<n;i++)
                 ^
sorting.cpp:20:13: note: shadowed declaration is here
     for(int i=0;i<m;i++){
             ^
sorting.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
sorting.cpp:43:33: warning: 'idfrom' may be used uninitialized in this function [-Wmaybe-uninitialized]
             swap(a[idx],a[idfrom]);
                                 ^
sorting.cpp:43:23: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
             swap(a[idx],a[idfrom]);
                       ^

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 376 KB Output is correct
7 Correct 2 ms 376 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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -