oj.uz

Submission #8551

# Submission time Handle Problem Language Result Execution time Memory
8551 2014-09-16T06:22:27 Z gs14004 Gondola (IOI14_gondola) C++
100 / 100
 72 ms 7360 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include "gondola.h"

using namespace std;
typedef pair<int,int> pi;

int valid(int n, int inputSeq[]){
    set<int> s;
    for (int i=0; i<n; i++) {
        if(s.find(inputSeq[i]) != s.end()) return 0;
        s.insert(inputSeq[i]);
    }
    int piv = -1;
    for (int i=0; i<n; i++) {
        if(inputSeq[i] <= n){
            if(piv == -1){
                piv = i;
            }
            else{
                int res = i + (inputSeq[piv] - piv) + n;
                res %= n;
                if(res == 0) res = n;
                if(inputSeq[i] != res) return 0;
            }
        }
    }
    return 1;
}

priority_queue<pi,vector<pi>,greater<pi> > pq, pq2;

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int piv = 0, piv2 = n+1, piv3 = 0;
    for (int i=0; i<n; i++) {
        if(gondolaSeq[i] <= n){
            piv = gondolaSeq[i] - i - 1+ n;
            piv %= n;
        }
    }
    int newSeq[100005] = {};
    for (int i=0; i<n; i++) {
        newSeq[i] = gondolaSeq[(i + n - piv)%n];
        if(newSeq[i] > n) pq.push(pi(newSeq[i],i+1));
    }
    while (!pq.empty()) {
        pi x = pq.top();
        pq.pop();
        replacementSeq[piv3++] = x.second;
        for (int i=piv2; i<x.first; i++) {
            replacementSeq[piv3++] = i;
        }
        piv2 = x.first + 1;
    }
    return piv3;
}

long long pow(int x, int time){
    long long res = 1, piv = x, mod = 1e9 + 9;
    while (time) {
        if(time&1) res *= piv;
        piv *= piv;
        res %= mod;
        piv %= mod;
        time >>= 1;
    }
    return res;
}

int newSeq[100005];
int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq)) return 0;
    int piv = 0, piv2 = n, cnt = 0;
    long long res = 1;
    for (int i=0; i<n; i++) {
        if(inputSeq[i] > n) newSeq[piv++] = inputSeq[i];
    }
    if(piv == n) res = piv;
    if(piv == 0) return 1;
    cnt = piv;
    sort(newSeq,newSeq+piv);
    for (int i=0; i<piv; i++) {
        res *= pow(cnt,newSeq[i] - piv2 - 1);
        piv2 = newSeq[i];
        cnt--;
        res %= 1000000009;
    }
    return (int)res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 20 ms 4720 KB Output is correct
7 Correct 12 ms 3004 KB Output is correct
8 Correct 36 ms 6304 KB Output is correct
9 Correct 4 ms 4060 KB Output is correct
10 Correct 36 ms 6832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 20 ms 4720 KB Output is correct
7 Correct 12 ms 3004 KB Output is correct
8 Correct 36 ms 6304 KB Output is correct
9 Correct 8 ms 4060 KB Output is correct
10 Correct 48 ms 6832 KB Output is correct
11 Correct 0 ms 3004 KB Output is correct
12 Correct 0 ms 3004 KB Output is correct
13 Correct 24 ms 4588 KB Output is correct
14 Correct 0 ms 3004 KB Output is correct
15 Correct 52 ms 6964 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 0 ms 3004 KB Output is correct
7 Correct 0 ms 3004 KB Output is correct
8 Correct 0 ms 3004 KB Output is correct
9 Correct 56 ms 6436 KB Output is correct
10 Correct 36 ms 5776 KB Output is correct
11 Correct 16 ms 3928 KB Output is correct
12 Correct 20 ms 4192 KB Output is correct
13 Correct 4 ms 3268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 0 ms 3004 KB Output is correct
7 Correct 0 ms 3004 KB Output is correct
8 Correct 0 ms 3004 KB Output is correct
9 Correct 40 ms 6436 KB Output is correct
10 Correct 40 ms 5776 KB Output is correct
11 Correct 16 ms 3928 KB Output is correct
12 Correct 16 ms 4192 KB Output is correct
13 Correct 4 ms 3268 KB Output is correct
14 Correct 72 ms 6832 KB Output is correct
15 Correct 72 ms 7360 KB Output is correct
16 Correct 12 ms 3796 KB Output is correct
17 Correct 44 ms 5908 KB Output is correct
18 Correct 24 ms 4588 KB Output is correct