oj.uz

Submission #707895

# Submission time Handle Problem Language Result Execution time Memory
707895 2023-03-10T11:24:20 Z ssense Gondola (IOI14_gondola) C++14
100 / 100
 54 ms 5908 KB 
#include <bits/stdc++.h>
#include "gondola.h"
typedef long long  ll;
using namespace std;
#define vint vector<int>
/*int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
 */

long long power(long long n, long long pow, long long m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;}

int valid(int n, int inputSeq[])
{
    set<int> s;
    int dif = -1;
    for(int i = 0; i < n; i++)
    {
        if(inputSeq[i] <= n)
        {
            if(dif == -1)
            {
                dif = (inputSeq[i]-(i+1)+n)%n;
            }
            if((inputSeq[i]-(i+1)+n)%n != dif)
            {
                return 0;
            }
        }
        if(s.count(inputSeq[i]))
        {
            return 0;
        }
        s.insert(inputSeq[i]);
    }
    return 1;
}
 
int replacement(int n, int gondolaSeq[], int ans[])
{
    vector<pair<int, int>> to_replace;
    for(int i = 0; i < n; i++)
    {
        gondolaSeq[i]--;
    }
    for(int i = 0; i < n; i++)
    {
        if(gondolaSeq[i] < n)
        {
            for(int j = 1; j < n; j++)
            {
                if(gondolaSeq[(i+j)%n] >= n)
                {
                    to_replace.push_back({gondolaSeq[(i+j)%n], (gondolaSeq[i]+j)%n});
                }
            }
            break;
        }
    }
    if(to_replace.empty() && gondolaSeq[0] >= n)
    {
        for(int i = 0; i < n; i++)
        {
            to_replace.push_back({gondolaSeq[i], i});
        }
    }
    sort(to_replace.begin(), to_replace.end());
    int count = 0;
    for(auto x : to_replace)
    {
        while(x.second != x.first)
        {
            ans[count] = x.second+1;
            x.second = n+count;
            count++;
        }
    }
    return count;
}
 
int countReplacement(int n, int inputSeq[])
{
    if(!valid(n, inputSeq))
    {
        return 0;
    }
    vector<pair<int, int>> to_replace;
    for(int i = 0; i < n; i++)
    {
        inputSeq[i]--;
    }
    for(int i = 0; i < n; i++)
    {
        if(inputSeq[i] < n)
        {
            for(int j = 1; j < n; j++)
            {
                if(inputSeq[(i+j)%n] >= n)
                {
                    to_replace.push_back({inputSeq[(i+j)%n], (inputSeq[i]+j)%n});
                }
            }
            break;
        }
    }
    long long ans = 1;
    if(to_replace.empty() && inputSeq[0] >= n)
    {
        for(int i = 0; i < n; i++)
        {
            to_replace.push_back({inputSeq[i], i});
        }
        ans = n;
    }
    to_replace.push_back({n-1, 0});
    sort(to_replace.begin(), to_replace.end());
    for(int i = 1; i < to_replace.size(); i++)
    {
        ans*=power(to_replace.size()-i, to_replace[i].first-to_replace[i-1].first-1, 1000000009);
        ans%=1000000009;
    }
    return (int)ans;
}
 /*
int32_t main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << countReplacement(n, a);
}
*/

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 12 ms 2132 KB Output is correct
7 Correct 9 ms 608 KB Output is correct
8 Correct 23 ms 3924 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 32 ms 4488 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 13 ms 2132 KB Output is correct
7 Correct 9 ms 612 KB Output is correct
8 Correct 23 ms 3868 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 30 ms 4496 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 9 ms 596 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 520 KB Output is correct
12 Correct 10 ms 648 KB Output is correct
13 Correct 12 ms 1156 KB Output is correct
14 Correct 8 ms 596 KB Output is correct
15 Correct 17 ms 2204 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 44 ms 4048 KB Output is correct
10 Correct 30 ms 3276 KB Output is correct
11 Correct 11 ms 1432 KB Output is correct
12 Correct 14 ms 1640 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 38 ms 3900 KB Output is correct
10 Correct 31 ms 3300 KB Output is correct
11 Correct 11 ms 1364 KB Output is correct
12 Correct 14 ms 1692 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 47 ms 4520 KB Output is correct
15 Correct 54 ms 5908 KB Output is correct
16 Correct 9 ms 1340 KB Output is correct
17 Correct 35 ms 4040 KB Output is correct
18 Correct 19 ms 2740 KB Output is correct