oj.uz

Submission #30943

# Submission time Handle Problem Language Result Execution time Memory
30943 2017-08-02T00:59:02 Z kajebiii Gondola (IOI14_gondola) C++14
75 / 100
 33 ms 5792 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;

const int MAX_N = 1e5 + 100;
int temp[MAX_N];
int valid(int n, int nr[]) {
    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;
    }
    sort(temp, temp+n);
    for(int i=0; i+1<n; i++) if(temp[i] == temp[i+1]) return 0;

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

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


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;
}

//----------------------
const int MOD = 1e9 + 9;

int myTemp[MAX_N];
int countReplacement(int n, int nr[]) {
    for(int i=0; i<n; i++) myTemp[i] = nr[i];
    if(valid(n, myTemp) == 0) {
        return 0;
    }
    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("");

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

    int unCh = n;
    int now = n;
    int ans = 1;
    for(int i=0; i<n; i++) {
        while(now < ps[i].one) {
            now++;
            if(now != ps[i].one)
                ans = 1ll * ans * unCh % MOD;
        }
        unCh--;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:23:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:86: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 4172 KB Output is correct
2 Correct 0 ms 4172 KB Output is correct
3 Correct 0 ms 4172 KB Output is correct
4 Correct 0 ms 4172 KB Output is correct
5 Correct 0 ms 4172 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4172 KB Output is correct
2 Correct 0 ms 4172 KB Output is correct
3 Correct 0 ms 4172 KB Output is correct
4 Correct 0 ms 4172 KB Output is correct
5 Correct 0 ms 4172 KB Output is correct
6 Correct 0 ms 4172 KB Output is correct
7 Correct 0 ms 4172 KB Output is correct
8 Correct 0 ms 4172 KB Output is correct
9 Correct 23 ms 5792 KB Output is correct
10 Correct 23 ms 5024 KB Output is correct
11 Correct 6 ms 4640 KB Output is correct
12 Correct 9 ms 4640 KB Output is correct
13 Incorrect 3 ms 4312 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4172 KB Output is correct
2 Correct 0 ms 4172 KB Output is correct
3 Correct 0 ms 4172 KB Output is correct
4 Correct 0 ms 4172 KB Output is correct
5 Correct 0 ms 4172 KB Output is correct
6 Correct 0 ms 4172 KB Output is correct
7 Correct 0 ms 4172 KB Output is correct
8 Correct 0 ms 4172 KB Output is correct
9 Correct 33 ms 5792 KB Output is correct
10 Correct 23 ms 5024 KB Output is correct
11 Correct 9 ms 4640 KB Output is correct
12 Correct 9 ms 4640 KB Output is correct
13 Incorrect 3 ms 4312 KB Output isn't correct
14 Halted 0 ms 0 KB -