oj.uz

Submission #1064392

# Submission time Handle Problem Language Result Execution time Memory
1064392 2024-08-18T12:09:11 Z anango Gondola (IOI14_gondola) C++17
100 / 100
 59 ms 9680 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000009;

signed valid(signed n, signed inputSeq[]) {
    vector<int> pos(n,-1);
    set<int> seen;
    for (int i=0; i<n; i++) {
        if (inputSeq[i]<=n) {
            pos[inputSeq[i]-1] = i;
        }
        if (seen.count(inputSeq[i]-1)) {
            return 0;   
        }
        seen.insert(inputSeq[i]-1);
    }
    set<int> S;
    for (int i=0; i<n; i++) {
        if (pos[i]!=-1) {
            S.insert((pos[i]-i+n)%n);
        }
    }
    return S.size()<=1;
}

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

signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]) {
    vector<pair<int,int>> posindex;
    vector<int> actual(n,-1);
    for (int i=0; i<n; i++) {
        if (gondolaSeq[i]<=n) {
            for (int j=0; j<n; j++) {
                actual[j] = (gondolaSeq[i]-1+j-i+3*n)%n;
            }
            break;
        }
    }
    if (actual[0]==-1) {
        for (int i=0; i<n; i++) actual[i] = i;
    }
    for (int i=0; i<n; i++) {
        //cout << actual[i] <<" ";
    }
    //cout << endl;
    for (int i=0; i<n; i++) {
        posindex.push_back({gondolaSeq[i]-1,i});
    }
    sort(posindex.begin(), posindex.end());
    vector<int> repl;
    int cur = n;
    for (int i=0; i<posindex.size(); i++) {
        while (posindex[i].first>=cur) {
            repl.push_back(actual[posindex[i].second]);
            actual[posindex[i].second] = cur;
            cur++;
        }
    }
    for (int i=0; i<repl.size(); i++) {
        replacementSeq[i] = repl[i]+1;
    }
    //cout << "done " << repl.size() << endl;
    return repl.size();
}

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


int exp(int base, int exponent) {
    int p = 1;
    int t = base;
    for (int i=0; i<40; i++) {
        if (exponent&(1LL<<i)) {
            p*=t; p%=MOD;
        }
        t*=t; t%=MOD;
    }
    return p;
}

signed countReplacement(signed n, signed inputSeq[]) {
    vector<int> pos(n,-1);
    set<int> seen;
    for (int i=0; i<n; i++) {
        if (inputSeq[i]<=n) {
            pos[inputSeq[i]-1] = i;
        }
        if (seen.count(inputSeq[i]-1)) {
            return 0;   
        }
        seen.insert(inputSeq[i]-1);
    }
    set<int> S;
    for (int i=0; i<n; i++) {
        if (pos[i]!=-1) {
            S.insert((pos[i]-i+n)%n);
        }
    }
    if (S.size()>1) {
        return 0;
    }

    int prod = 1;
    vector<pair<int,int>> posindex;
    vector<int> actual(n,-1);
    for (int i=0; i<n; i++) {
        if (inputSeq[i]<=n) {
            for (int j=0; j<n; j++) {
                actual[j] = (inputSeq[i]-1+j-i+3*n)%n;
            }
            break;
        }
    }
    if (actual[0]==-1) {
        prod = n; //multiply by n at the end
        for (int i=0; i<n; i++) actual[i] = i;
    }
    for (int i=0; i<n; i++) {
        //cout << actual[i] <<" ";
    }
    //cout << endl;
    for (int i=0; i<n; i++) {
        posindex.push_back({inputSeq[i]-1,i});
    }
    sort(posindex.begin(), posindex.end());
    int cur = n;
    for (int i=0; i<posindex.size(); i++) {
        if (posindex[i].first>=cur) {
            prod*=exp(n-i,posindex[i].first-cur);
            prod%=MOD;
            cur=posindex[i].first+1;
        }
    }
    //cout << "done " << repl.size() << endl;
    return (signed)prod;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:54:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i=0; i<posindex.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~
gondola.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i=0; i<repl.size(); i++) {
      |                   ~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:129:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i=0; i<posindex.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 10 ms 2876 KB Output is correct
7 Correct 6 ms 1884 KB Output is correct
8 Correct 19 ms 4868 KB Output is correct
9 Correct 6 ms 1880 KB Output is correct
10 Correct 23 ms 5724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 2652 KB Output is correct
7 Correct 6 ms 1884 KB Output is correct
8 Correct 17 ms 4952 KB Output is correct
9 Correct 6 ms 1880 KB Output is correct
10 Correct 24 ms 5624 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 12 ms 2564 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 39 ms 7288 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 404 KB Output is correct
11 Correct 12 ms 3792 KB Output is correct
12 Correct 10 ms 4048 KB Output is correct
13 Correct 11 ms 3000 KB Output is correct
14 Correct 8 ms 3792 KB Output is correct
15 Correct 15 ms 3152 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 50 ms 7972 KB Output is correct
10 Correct 32 ms 5836 KB Output is correct
11 Correct 13 ms 2524 KB Output is correct
12 Correct 15 ms 3036 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 44 ms 8008 KB Output is correct
10 Correct 34 ms 5836 KB Output is correct
11 Correct 12 ms 2524 KB Output is correct
12 Correct 16 ms 3044 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct
14 Correct 55 ms 8840 KB Output is correct
15 Correct 59 ms 9680 KB Output is correct
16 Correct 10 ms 2264 KB Output is correct
17 Correct 40 ms 6420 KB Output is correct
18 Correct 22 ms 4268 KB Output is correct