oj.uz

Submission #30945

# Submission time Handle Problem Language Result Execution time Memory
30945 2017-08-02T01:03:06 Z kajebiii Gondola (IOI14_gondola) C++14
100 / 100
 43 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 pow(int a, int b) {
    int res = 1, p = a;
    while(b) {
        if(b&1) res = 1ll * res * p % MOD;
        p = 1ll * p * p % MOD;
        b >>= 1;
    }
    return res;
}
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;
    }
    int ans = 1;
    if(ix != -1) {
        ix = (ix + n - (nr[ix]-1)) % n;
        for(int i=0; i<n; i++) nr[i] = temp[(i+ix)%n];
    }else ans = 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;
    for(int i=0; i<n; i++) {
        if(now < ps[i].one) {
            ans = 1ll * ans * pow(unCh, ps[i].one-now-1) % MOD;
            now = ps[i].one;
        }
        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:95: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 13 ms 4172 KB Output is correct
7 Correct 23 ms 4172 KB Output is correct
8 Correct 9 ms 4172 KB Output is correct
9 Correct 3 ms 4172 KB Output is correct
10 Correct 16 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 9 ms 4172 KB Output is correct
7 Correct 19 ms 4172 KB Output is correct
8 Correct 6 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 9 ms 4172 KB Output is correct
14 Correct 0 ms 4172 KB Output is correct
15 Correct 23 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 9 ms 5792 KB Output is correct
12 Correct 13 ms 5792 KB Output is correct
13 Correct 16 ms 5024 KB Output is correct
14 Correct 16 ms 5792 KB Output is correct
15 Correct 26 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
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
9 Correct 29 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 13 ms 4640 KB Output is correct
13 Correct 3 ms 4312 KB Output is correct

Subtask #10
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 23 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 Correct 0 ms 4312 KB Output is correct
14 Correct 33 ms 5792 KB Output is correct
15 Correct 43 ms 5792 KB Output is correct
16 Correct 6 ms 4640 KB Output is correct
17 Correct 23 ms 5024 KB Output is correct
18 Correct 13 ms 5024 KB Output is correct