답안 #8532 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8532	2014-09-16T05:46:56 Z	gs14004	곤돌라 (IOI14_gondola)	C++	90 / 100	32 ms	3856 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[]){
    int v[250005]={};
    for (int i=0; i<n; i++) {
        if(v[inputSeq[i]]) return 0;
        v[inputSeq[i]] = 1;
    }
    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;
set<int> mp;

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){
    if(time < 0) return 1ll;
    long long res = 1, piv = x;
    while (time) {
        if(time&1) res *= piv;
        piv *= piv;
        res %= 1000000009ll;
        piv %= 1000000009ll;
        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 %= 1000000009ll;
    }
    return res%1000000009;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3852 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3848 KB	Output is correct
4	Correct	0 ms	3848 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	4 ms	3852 KB	Output is correct
7	Correct	12 ms	3856 KB	Output is correct
8	Correct	12 ms	3856 KB	Output is correct
9	Correct	0 ms	3852 KB	Output is correct
10	Correct	12 ms	3856 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3848 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3848 KB	Output is correct
4	Correct	0 ms	3848 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	4 ms	3852 KB	Output is correct
7	Correct	8 ms	3848 KB	Output is correct
8	Correct	12 ms	3856 KB	Output is correct
9	Correct	4 ms	3852 KB	Output is correct
10	Correct	8 ms	3856 KB	Output is correct
11	Correct	0 ms	3848 KB	Output is correct
12	Correct	0 ms	3852 KB	Output is correct
13	Correct	4 ms	3852 KB	Output is correct
14	Correct	0 ms	3852 KB	Output is correct
15	Correct	16 ms	3852 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3000 KB	Output is correct
2	Correct	0 ms	3000 KB	Output is correct
3	Correct	0 ms	3000 KB	Output is correct
4	Correct	0 ms	3000 KB	Output is correct
5	Correct	0 ms	3000 KB	Output is correct
6	Correct	0 ms	3000 KB	Output is correct
7	Correct	0 ms	3000 KB	Output is correct
8	Correct	0 ms	3000 KB	Output is correct
9	Correct	0 ms	3000 KB	Output is correct
10	Correct	0 ms	3000 KB	Output is correct
11	Correct	8 ms	3000 KB	Output is correct
12	Correct	12 ms	3000 KB	Output is correct
13	Correct	12 ms	3388 KB	Output is correct
14	Correct	8 ms	3000 KB	Output is correct
15	Correct	32 ms	3388 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3852 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3852 KB	Output is correct
4	Correct	0 ms	3852 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	0 ms	3848 KB	Output is correct
7	Correct	0 ms	3852 KB	Output is correct
8	Correct	0 ms	3856 KB	Output is correct
9	Correct	16 ms	3856 KB	Output is correct
10	Correct	12 ms	3852 KB	Output is correct
11	Correct	4 ms	3852 KB	Output is correct
12	Correct	8 ms	3852 KB	Output is correct
13	Correct	0 ms	3848 KB	Output is correct

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3852 KB	Output is correct
2	Correct	0 ms	3856 KB	Output is correct
3	Correct	0 ms	3852 KB	Output is correct
4	Correct	0 ms	3852 KB	Output is correct
5	Correct	0 ms	3848 KB	Output is correct
6	Correct	0 ms	3848 KB	Output is correct
7	Correct	0 ms	3848 KB	Output is correct
8	Correct	0 ms	3852 KB	Output is correct
9	Correct	16 ms	3848 KB	Output is correct
10	Correct	16 ms	3856 KB	Output is correct
11	Correct	4 ms	3852 KB	Output is correct
12	Correct	8 ms	3852 KB	Output is correct
13	Correct	0 ms	3848 KB	Output is correct
14	Runtime error	16 ms	3852 KB	SIGBUS Bus error
15	Halted	0 ms	0 KB	-

답안 #8532

Compilation message