oj.uz

Submission #30941

# Submission time Handle Problem Language Result Execution time Memory
30941 2017-08-02T00:45:46 Z kajebiii Gondola (IOI14_gondola) C++14
55 / 100
 19 ms 5400 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; 
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

int valid(int n, int nr[]) {
    int ix = -1, cnt = 0;
    for(int i=0; i<n; i++) if(nr[i] >= 1 && nr[i] <= n) {
        ix = i;
        break;
    }
    if(ix == -1) {
        sort(nr, nr+n);
        for(int i=0; i+1<n; i++) if(nr[i] == nr[i+1]) return 0;
        return 1;
    }
    ix = (ix + n - (nr[ix]-1)) % n;
    for(int i=0; i<n; i++) if(nr[(ix+i)%n] != (i+1)) return 0;
    return 1;
}

//----------------------

const int MAX_N = 1e5 + 100;

int temp[MAX_N];
int replacement(int n, int nr[], int res[]) {
    for(int i=0; i<n; i++) temp[i] = nr[i];

    int ix = -1, cnt = 0;
    for(int i=0; i<n; i++) if(nr[i] >= 1 && nr[i] <= n) {
        ix = i;
        break;
    }
    if(ix != -1) {
        ix = (ix + n - (nr[ix]-1)) % n;
        for(int i=0; i<n; i++) nr[i] = temp[(i+ix)%n];
    }
//    for(int i=0; i<n; i++) printf("%d ", nr[i]); puts("");

    int ansL = 0;
    vector<pi> ps;
    for(int i=0; i<n; i++) ps.push_back(pi(nr[i], i));
    sort(ALL(ps));
    for(int i=0; i<n; i++) nr[i] = i+1;

    int now = n;
    for(int i=0; i<n; i++) {
        while(now < ps[i].one) {
            now++;
            res[ansL++] = nr[ps[i].two];
            nr[ps[i].two] = now;
        }
    }
    return ansL;
}

//----------------------

int countReplacement(int n, int inputSeq[]) {
    return -3;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:20:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:43:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3780 KB Output is correct
2 Correct 0 ms 3780 KB Output is correct
3 Correct 0 ms 3780 KB Output is correct
4 Correct 0 ms 3780 KB Output is correct
5 Correct 0 ms 3780 KB Output is correct
6 Correct 0 ms 3780 KB Output is correct
7 Correct 0 ms 3780 KB Output is correct
8 Correct 0 ms 3780 KB Output is correct
9 Correct 0 ms 3780 KB Output is correct
10 Correct 0 ms 3780 KB Output is correct
11 Correct 13 ms 5400 KB Output is correct
12 Correct 19 ms 5400 KB Output is correct
13 Correct 16 ms 4632 KB Output is correct
14 Correct 16 ms 5400 KB Output is correct
15 Correct 19 ms 4248 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3780 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3780 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3780 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3780 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -