oj.uz

Submission #67219

# Submission time Handle Problem Language Result Execution time Memory
67219 2018-08-13T16:28:01 Z MKopchev Gondola (IOI14_gondola) C++14
100 / 100
 198 ms 10188 KB 
#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int mod=1e9+9;
int valid(int n, int inputSeq[])
{
    set<int> uniq={};
    for(int i=0;i<n;i++)
        uniq.insert(inputSeq[i]);
    if(uniq.size()!=n)return 0;
    int mini=0;
    for(int i=1;i<n;i++)
        if(inputSeq[mini]>inputSeq[i])mini=i;
    int ind=(mini+1)%n;
    int value=-1;
    int target=inputSeq[mini];
    while(ind!=mini)
    {
        value=inputSeq[ind];
        target++;
        if(value<target)return 0;
        if(value<=n&&target<=n)
        {
            if(value!=target)return 0;
        }
        ind=(ind+1)%n;
    }
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int mini=0;
    for(int i=1;i<n;i++)
        if(gondolaSeq[mini]>gondolaSeq[i])mini=i;
        map<int/*number you are aiming at*/,int/*where you begin*/> start={};
    if(gondolaSeq[mini]>n)
    {
        for(int i=0;i<n;i++)
            start[gondolaSeq[i]]=i+1;
    }
    else
    {
        int value=gondolaSeq[mini],t=0;
        for(int i=mini;i!=mini||t==0;i=(i+1)%n)
        {
            start[gondolaSeq[i]]=value;
            value++;
            if(value>n)value=1;
            t++;
        }
    }
    int prev=n,ind=0;
    //for(auto k:start)cout<<k.first<<" "<<k.second<<endl;
    for(auto k:start)
    {
        if(k.first!=k.second)
        {
            replacementSeq[ind++]=k.second;
            prev++;
            while(prev!=k.first)
            {
                replacementSeq[ind++]=prev;
                prev++;
            }
        }
        prev=max(prev,k.first);
    }

    //cout<<ind<<" : ";for(int i=0;i<ind;i++)cout<<replacementSeq[i]<<" ";cout<<endl;
    return ind;
}
long long my_pow(long long a,long long b)
{
    if(b==0)return 1;
    long long c=my_pow(a,b/2);
    if(b%2==0)return c*c%mod;
    return c*c%mod*a%mod;
}
int countReplacement(int n, int inputSeq[])
{
    if(valid(n,inputSeq)==0)return 0;
    int mini=0;
    for(int i=1;i<n;i++)
        if(inputSeq[mini]>inputSeq[i])mini=i;
    set<int> integers={};
    long long result=1;
    if(inputSeq[mini]>n)
    {
        result=n;
        for(int i=0;i<n;i++)
            integers.insert(inputSeq[i]);
    }
    else
    {
            int value=inputSeq[mini],t=0;
        for(int i=mini;i!=mini||t==0;i=(i+1)%n)
        {
            if(inputSeq[i]!=value)integers.insert(inputSeq[i]);
            value++;
            if(value>n)value=1;
            t++;
        }
    }
    int prev=n,active=integers.size();
    for(auto k:integers)
    {
        result=result*my_pow(active,k-prev-1)%mod;
        prev=k;
        active--;
    }
    return result;
}
/*
int n=4;
int v[]={1, 2, 7, 6};
int arr[7];
int main()
{
    cout<<countReplacement(n,v)<<endl;
}
*/

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(uniq.size()!=n)return 0;
        ~~~~~~~~~~~^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:33:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<n;i++)
     ^~~
gondola.cpp:35:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         map<int/*number you are aiming at*/,int/*where you begin*/> start={};
         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 3 ms 560 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 17 ms 2508 KB Output is correct
7 Correct 44 ms 4048 KB Output is correct
8 Correct 37 ms 4172 KB Output is correct
9 Correct 16 ms 4172 KB Output is correct
10 Correct 37 ms 4860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4860 KB Output is correct
2 Correct 3 ms 4860 KB Output is correct
3 Correct 3 ms 4860 KB Output is correct
4 Correct 3 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct
6 Correct 18 ms 4860 KB Output is correct
7 Correct 44 ms 4860 KB Output is correct
8 Correct 38 ms 4860 KB Output is correct
9 Correct 12 ms 4860 KB Output is correct
10 Correct 43 ms 4860 KB Output is correct
11 Correct 2 ms 4860 KB Output is correct
12 Correct 3 ms 4860 KB Output is correct
13 Correct 25 ms 4860 KB Output is correct
14 Correct 3 ms 4860 KB Output is correct
15 Correct 67 ms 4988 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 3 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 3 ms 4988 KB Output is correct
5 Correct 2 ms 4988 KB Output is correct
6 Correct 3 ms 4988 KB Output is correct
7 Correct 3 ms 4988 KB Output is correct
8 Correct 3 ms 4988 KB Output is correct
9 Correct 2 ms 4988 KB Output is correct
10 Correct 3 ms 4988 KB Output is correct
11 Correct 37 ms 4988 KB Output is correct
12 Correct 58 ms 5164 KB Output is correct
13 Correct 35 ms 5164 KB Output is correct
14 Correct 37 ms 5164 KB Output is correct
15 Correct 30 ms 5164 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5164 KB Output is correct
2 Correct 2 ms 5164 KB Output is correct
3 Correct 2 ms 5164 KB Output is correct
4 Correct 2 ms 5164 KB Output is correct
5 Correct 3 ms 5164 KB Output is correct
6 Correct 2 ms 5164 KB Output is correct
7 Correct 3 ms 5164 KB Output is correct
8 Correct 2 ms 5164 KB Output is correct
9 Correct 88 ms 5236 KB Output is correct
10 Correct 59 ms 5236 KB Output is correct
11 Correct 24 ms 5236 KB Output is correct
12 Correct 29 ms 5236 KB Output is correct
13 Correct 7 ms 5236 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5236 KB Output is correct
2 Correct 3 ms 5236 KB Output is correct
3 Correct 3 ms 5236 KB Output is correct
4 Correct 3 ms 5236 KB Output is correct
5 Correct 2 ms 5236 KB Output is correct
6 Correct 2 ms 5236 KB Output is correct
7 Correct 2 ms 5236 KB Output is correct
8 Correct 2 ms 5236 KB Output is correct
9 Correct 82 ms 6584 KB Output is correct
10 Correct 79 ms 6584 KB Output is correct
11 Correct 29 ms 6584 KB Output is correct
12 Correct 34 ms 6584 KB Output is correct
13 Correct 8 ms 6584 KB Output is correct
14 Correct 136 ms 8804 KB Output is correct
15 Correct 198 ms 10188 KB Output is correct
16 Correct 22 ms 10188 KB Output is correct
17 Correct 84 ms 10188 KB Output is correct
18 Correct 42 ms 10188 KB Output is correct