답안 #8551 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8551	2014-09-16T06:22:27 Z	gs14004	곤돌라 (IOI14_gondola)	C++	100 / 100	72 ms	7360 KB

gondola

#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

#	결과	메모리	Grader output
1	Correct	3004 KB	Output is correct
2	Correct	3004 KB	Output is correct
3	Correct	3004 KB	Output is correct
4	Correct	3004 KB	Output is correct
5	Correct	3004 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	3004 KB	Output is correct
2	Correct	3004 KB	Output is correct
3	Correct	3004 KB	Output is correct
4	Correct	3004 KB	Output is correct
5	Correct	3004 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	3004 KB	Output is correct
2	Correct	3004 KB	Output is correct
3	Correct	3004 KB	Output is correct
4	Correct	3004 KB	Output is correct
5	Correct	3004 KB	Output is correct
6	Correct	3004 KB	Output is correct
7	Correct	3004 KB	Output is correct
8	Correct	3004 KB	Output is correct
9	Correct	3004 KB	Output is correct
10	Correct	3004 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	3004 KB	Output is correct
2	Correct	3004 KB	Output is correct
3	Correct	3004 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	메모리	Grader output
1	Correct	3004 KB	Output is correct
2	Correct	3004 KB	Output is correct
3	Correct	3004 KB	Output is correct
4	Correct	3004 KB	Output is correct
5	Correct	3004 KB	Output is correct
6	Correct	3004 KB	Output is correct
7	Correct	3004 KB	Output is correct
8	Correct	3004 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #8551

Compilation message