oj.uz

Submission #67261

# Submission time Handle Problem Language Result Execution time Memory
67261 2018-08-13T18:20:29 Z theknife2001 Gondola (IOI14_gondola) C++17
75 / 100
 24 ms 10268 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;
const int N=250055;
int a[N];
int b[N];
priority_queue < int > pq;

int valid(int n, int inputSeq[])
{

    int j=0,x=1e9;
    for(int i=0;i<n;i++)
    {
        a[inputSeq[i]]++;
        if(x>inputSeq[i])
        {
            x=inputSeq[i];
            j=i;
        }
        if(a[inputSeq[i]]>1)
            return 0;
    }
    x++;
    for(int i=j+1;i<n;i++)
    {
        if(inputSeq[i]<=n)
        {
            if(inputSeq[i]==x)
            {
                x++;
                continue ;
            }
            return 0;
        }
        if(a[x]==0)
            x++;
        else
            return 0;
    }
    for(int i=0;i<j;i++)
    {
        if(inputSeq[i]<=n)
        {
            if(inputSeq[i]==x)
            {
                x++;
                continue ;
            }
            return 0;
        }
        if(a[x]==0)
            x++;
        else
            return 0;
    }
    return 1;

}



int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    bool q=0;
    for(int i=0;i<n;i++)
    {
        a[gondolaSeq[i]]=i+1;
        if(!q&&gondolaSeq[i]<=n)
        {
            q=1;
            int x=gondolaSeq[i];
            for(int j=i;j<n;j++)
            {
                b[j]=x;
                x++;
                if(x>n)
                    x=1;
            }
            for(int j=0;j<i;j++)
            {
                b[j]=x++;
                if(x>n)
                    x=1;
            }
        }
    }
    if(!q)
        for(int i=0;i<n;i++)
            b[i]=i+1;
    int x=n+1;
    int j=0;
    for(int i=n+1;i<N;i++)
    {
        if(!a[i])
            continue ;
        a[i]--;
        while(b[a[i]]!=i)
        {
            replacementSeq[j++]=b[a[i]];
            b[a[i]]=x;
            x++;
        }
    }
    return j;
}

int m=1e9+9;


long long pow(long long x, int i)
{
    if(i%2)
        return (pow(x,i-1)*x)%m;
    if(i==0)
        return 1;
    long long y=pow(x,i/2)%m;
    return (y*y)%m;
}


int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq))
        return 0;
    bool q=0;
    memset(a,0,sizeof a);
    for(int i=0;i<n;i++)
    {
        a[inputSeq[i]]=i+1;
        if(!q&&inputSeq[i]<=n)
        {
            q=1;
            int x=inputSeq[i];
            for(int j=i;j<n;j++)
            {
                b[j]=x;
                x++;
                if(x>n)
                    x=1;
            }
            for(int j=0;j<i;j++)
            {
                b[j]=x++;
                if(x>n)
                    x=1;
            }
        }
    }
    if(!q)
        for(int i=0;i<n;i++)
            b[i]=i+1;
    int x=n+1;
    long long ans=1;
    long long cnt=0;
    for(int i=n+1;i<N;i++)
        if(a[i])
            cnt++;
    int last=n;
    for(int i=n+1;i<N;i++)
    {
        if(!a[i]||cnt==0)
            continue ;
        a[i]--;
        ans*=pow(cnt,(inputSeq[a[i]]-last)-1);
        ans%=m;
        last=inputSeq[a[i]];
        cnt--;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:154:9: warning: unused variable 'x' [-Wunused-variable]
     int x=n+1;
         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 2 ms 496 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 496 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 8 ms 1080 KB Output is correct
7 Correct 15 ms 1932 KB Output is correct
8 Correct 12 ms 2296 KB Output is correct
9 Correct 6 ms 2296 KB Output is correct
10 Correct 14 ms 2940 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2940 KB Output is correct
2 Correct 2 ms 2940 KB Output is correct
3 Correct 2 ms 2940 KB Output is correct
4 Correct 2 ms 2940 KB Output is correct
5 Correct 2 ms 2940 KB Output is correct
6 Correct 7 ms 2940 KB Output is correct
7 Correct 14 ms 3780 KB Output is correct
8 Correct 11 ms 4012 KB Output is correct
9 Correct 5 ms 4012 KB Output is correct
10 Correct 13 ms 4704 KB Output is correct
11 Correct 3 ms 4704 KB Output is correct
12 Correct 2 ms 4704 KB Output is correct
13 Correct 8 ms 5296 KB Output is correct
14 Correct 2 ms 5296 KB Output is correct
15 Correct 17 ms 5528 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5528 KB Output is correct
2 Correct 3 ms 5528 KB Output is correct
3 Correct 2 ms 5528 KB Output is correct
4 Correct 3 ms 5528 KB Output is correct
5 Correct 2 ms 5528 KB Output is correct
6 Correct 2 ms 5528 KB Output is correct
7 Correct 2 ms 5528 KB Output is correct
8 Correct 3 ms 5528 KB Output is correct
9 Correct 3 ms 5528 KB Output is correct
10 Correct 3 ms 5528 KB Output is correct
11 Correct 13 ms 6276 KB Output is correct
12 Correct 15 ms 6984 KB Output is correct
13 Correct 16 ms 7500 KB Output is correct
14 Correct 13 ms 7500 KB Output is correct
15 Correct 24 ms 8916 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 3 ms 8916 KB Output is correct
3 Correct 3 ms 8916 KB Output is correct
4 Correct 3 ms 8916 KB Output is correct
5 Correct 3 ms 8916 KB Output is correct
6 Correct 3 ms 8916 KB Output is correct
7 Correct 4 ms 8916 KB Output is correct
8 Correct 3 ms 8916 KB Output is correct
9 Correct 20 ms 8916 KB Output is correct
10 Correct 16 ms 8968 KB Output is correct
11 Correct 9 ms 8968 KB Output is correct
12 Correct 10 ms 9008 KB Output is correct
13 Incorrect 3 ms 9008 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9008 KB Output is correct
2 Correct 3 ms 9008 KB Output is correct
3 Correct 3 ms 9008 KB Output is correct
4 Correct 3 ms 9008 KB Output is correct
5 Correct 3 ms 9008 KB Output is correct
6 Correct 3 ms 9008 KB Output is correct
7 Correct 4 ms 9008 KB Output is correct
8 Correct 3 ms 9008 KB Output is correct
9 Correct 19 ms 9888 KB Output is correct
10 Correct 17 ms 10252 KB Output is correct
11 Correct 9 ms 10252 KB Output is correct
12 Correct 13 ms 10268 KB Output is correct
13 Incorrect 5 ms 10268 KB Output isn't correct
14 Halted 0 ms 0 KB -