oj.uz

Submission #849722

# Submission time Handle Problem Language Result Execution time Memory
849722 2023-09-15T08:33:41 Z abcvuitunggio Gondola (IOI14_gondola) C++17
75 / 100
 35 ms 7504 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

map <int, int> mp;
set <int> s;

int valid(int n, int inputSeq[])
{
    int pos=0;
    for (int i=0;i<n;i++){
        if (mp.count(inputSeq[i]))
            return 0;
        if (inputSeq[pos]>inputSeq[i])
            pos=i;
        mp[inputSeq[i]]=1;
    }
    if (inputSeq[pos]>n)
        return 1;
    for (int i=0;i<n;i++)
        if (inputSeq[i]<=n&&((i-pos+n)%n+inputSeq[pos]-1)%n+1!=inputSeq[i])
            return 0;
    return 1;
}

//----------------------

int pos[250001],cur[100001];

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int val=0,p=0,mx=0;
    for (int i=0;i<n;i++){
        if (gondolaSeq[p]>gondolaSeq[i])
            p=i;
        mx=max(mx,gondolaSeq[i]);
    }
    if (gondolaSeq[p]>n)
        val=1,p=0;
    else
        val=gondolaSeq[p];
    for (int i=0;i<n;i++){
        int j=((i-p+n)%n+val-1)%n+1;
        pos[gondolaSeq[i]]=j;
        cur[j]=j;
        s.insert(i+1);
    }
    for (int i=0;i<n;i++)
        if (gondolaSeq[i]<=n)
            s.erase(gondolaSeq[i]);
    int l=0;
    for (int i=n+1;i<=mx;i++){
        if (!pos[i])
            pos[i]=*s.begin();
        else
            s.erase(pos[i]);

        replacementSeq[l]=cur[pos[i]];
        l++;
        cur[pos[i]]=i;
    }
    return l;
}

//----------------------

const int mod=1000000009;
vector <int> v;

int pw(int a, int b){
    if (!b)
        return 1;
    int t=pw(a,b>>1);
    t=1LL*t*t%mod;
    return (b&1?1LL*t*a%mod:t);
}

int countReplacement(int n, int inputSeq[])
{
    if (!valid(n,inputSeq))
        return 0;
    for (int i=0;i<n;i++)
        if (inputSeq[i]>n)
            v.push_back(inputSeq[i]);
    v.push_back(n);
    sort(v.begin(),v.end());
    int res=1;
    for (int i=1;i<v.size();i++)
        res=1LL*res*pw(v.size()-i,v[i]-v[i-1]-1)%mod;
    return res;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i=1;i<v.size();i++)
      |                  ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct
7 Correct 6 ms 2648 KB Output is correct
8 Correct 24 ms 5976 KB Output is correct
9 Correct 6 ms 3416 KB Output is correct
10 Correct 22 ms 6488 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 10 ms 4184 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 20 ms 5976 KB Output is correct
9 Correct 7 ms 3416 KB Output is correct
10 Correct 25 ms 6488 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 13 ms 4440 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 31 ms 6744 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2400 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 22 ms 6992 KB Output is correct
12 Correct 25 ms 7504 KB Output is correct
13 Correct 22 ms 4944 KB Output is correct
14 Correct 21 ms 7068 KB Output is correct
15 Correct 19 ms 4436 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 33 ms 6488 KB Output is correct
10 Correct 26 ms 5976 KB Output is correct
11 Correct 10 ms 3672 KB Output is correct
12 Correct 13 ms 4044 KB Output is correct
13 Incorrect 4 ms 2904 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 35 ms 6480 KB Output is correct
10 Correct 28 ms 5840 KB Output is correct
11 Correct 10 ms 3676 KB Output is correct
12 Correct 13 ms 4184 KB Output is correct
13 Incorrect 3 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -