oj.uz

Submission #31704

# Submission time Handle Problem Language Result Execution time Memory
31704 2017-08-31T13:07:41 Z top34051 Gondola (IOI14_gondola) C++14
100 / 100
 86 ms 8268 KB 
#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

# Verdict Execution time Memory 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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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