답안 #31704 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31704	2017-08-31T13:07:41 Z	top34051	곤돌라 (IOI14_gondola)	C++14	100 / 100	86 ms	8268 KB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define mod 1000000009LL

int n,m,mx;
int a[maxn];
set<int> vis;
map<int,int> s;

long long gpow(long long x,long long y) {
    if(y==0) return 1LL;
    if(y%2==0) return gpow((x*x)%mod,y/2);
    return (gpow(x,y-1)*x)%mod;
}

int valid(int N, int p[]) {
    int i, x = 0, val;
    n = N;
    //Build
    for(i=0;i<n;i++) if(p[i]<=n) x = i;
    val = p[x];
    for(i=0;i<n;i++) a[x] = val, x = (x+1)%n, val = val%n+1;
    //Check
    for(i=0;i<n;i++) if(p[i]<=n && a[i]!=p[i]) return 0;
    //Rep
    for(i=0;i<n;i++) {
        if(vis.find(p[i])!=vis.end()) return 0;
        vis.insert(p[i]);
    }
    return 1;
}

int replacement(int N, int p[], int res[]) {
    int i, x=-1, val;
    n = N;
    //Build
    for(i=0;i<n;i++) if(p[i]<=n) x = i;
    if(x==-1) val = 1, x = 0;
    else val = p[x];
    for(i=0;i<n;i++) a[x] = val, x = (x+1)%n, val = val%n+1;
    //Check
    for(i=0;i<n;i++) {
        mx = max(mx,p[i]);
        if(p[i]>n) s[p[i]] = i;
    }
    m = 0;
    for(i=n+1;i<=mx;i++) {
        if(s.find(i)!=s.end()) res[m++] = a[s[i]], a[s[i]] = i, s.erase(s.find(i));
        else if(s.size()>0) res[m++] = a[s.begin()->second], a[s.begin()->second] = i;
        else return 0;
    }
    return m;
}

int countReplacement(int N, int p[]) {
    int i, x=-1, val, cy;
    long long ans;
    n = N;
    //Build
    cy = 0;
    for(i=0;i<n;i++) if(p[i]<=n) x = i;
    if(x==-1) val = 1, x = 0, cy = 1;
    else val = p[x];
    for(i=0;i<n;i++) a[x] = val, x = (x+1)%n, val = val%n+1;
    //Check
    for(i=0;i<n;i++) if(p[i]<=n && a[i]!=p[i]) return 0;
    //Rep
    for(i=0;i<n;i++) {
        if(vis.find(p[i])!=vis.end()) return 0;
        vis.insert(p[i]);
    }
    //Check
    sort(&p[0],&p[n]);
    m = 0;
    for(i=0;i<n;i++) if(p[i]>n) m++;
    ans = 1;
    int last = n;
    for(i=0;i<n;i++) {
        x = p[i];
        if(x<=n) continue;
        ans = ((ans*gpow(m,x-last-1))%mod + mod)%mod;
//        printf("%d: m = %d\n",x,m);
        m--;
        last = x;
    }
    if(cy) ans = ((ans*n)%mod + mod)%mod;
    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3780 KB	Output is correct
2	Correct	0 ms	3780 KB	Output is correct
3	Correct	0 ms	3780 KB	Output is correct
4	Correct	0 ms	3780 KB	Output is correct
5	Correct	0 ms	3780 KB	Output is correct
6	Correct	16 ms	5496 KB	Output is correct
7	Correct	9 ms	3780 KB	Output is correct
8	Correct	36 ms	7080 KB	Output is correct
9	Correct	3 ms	4836 KB	Output is correct
10	Correct	43 ms	7740 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3780 KB	Output is correct
2	Correct	0 ms	3780 KB	Output is correct
3	Correct	0 ms	3780 KB	Output is correct
4	Correct	0 ms	3780 KB	Output is correct
5	Correct	0 ms	3780 KB	Output is correct
6	Correct	16 ms	5496 KB	Output is correct
7	Correct	13 ms	3780 KB	Output is correct
8	Correct	26 ms	7080 KB	Output is correct
9	Correct	6 ms	4836 KB	Output is correct
10	Correct	43 ms	7740 KB	Output is correct
11	Correct	0 ms	3780 KB	Output is correct
12	Correct	0 ms	3780 KB	Output is correct
13	Correct	0 ms	3780 KB	Output is correct
14	Correct	0 ms	3780 KB	Output is correct
15	Correct	16 ms	3780 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3780 KB	Output is correct
2	Correct	0 ms	3780 KB	Output is correct
3	Correct	0 ms	3780 KB	Output is correct
4	Correct	0 ms	3780 KB	Output is correct
5	Correct	0 ms	3780 KB	Output is correct
6	Correct	0 ms	3780 KB	Output is correct
7	Correct	0 ms	3780 KB	Output is correct
8	Correct	0 ms	3780 KB	Output is correct
9	Correct	53 ms	7212 KB	Output is correct
10	Correct	43 ms	6684 KB	Output is correct
11	Correct	13 ms	4836 KB	Output is correct
12	Correct	16 ms	5100 KB	Output is correct
13	Correct	3 ms	4044 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3780 KB	Output is correct
2	Correct	0 ms	3780 KB	Output is correct
3	Correct	0 ms	3780 KB	Output is correct
4	Correct	0 ms	3780 KB	Output is correct
5	Correct	0 ms	3780 KB	Output is correct
6	Correct	0 ms	3780 KB	Output is correct
7	Correct	0 ms	3780 KB	Output is correct
8	Correct	0 ms	3780 KB	Output is correct
9	Correct	59 ms	7212 KB	Output is correct
10	Correct	46 ms	6684 KB	Output is correct
11	Correct	16 ms	4836 KB	Output is correct
12	Correct	19 ms	5100 KB	Output is correct
13	Correct	3 ms	4044 KB	Output is correct
14	Correct	66 ms	7740 KB	Output is correct
15	Correct	86 ms	8268 KB	Output is correct
16	Correct	13 ms	4572 KB	Output is correct
17	Correct	49 ms	6816 KB	Output is correct
18	Correct	26 ms	5496 KB	Output is correct

답안 #31704

Compilation message