oj.uz

Submission #652274

# Submission time Handle Problem Language Result Execution time Memory
652274 2022-10-22T01:55:58 Z alvinpiter Gondola (IOI14_gondola) C++17
100 / 100
 49 ms 5008 KB 
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000009

LL fastExponentiation(LL base, LL p) {
  if (p == 0)
    return 1;

  LL half = fastExponentiation(base, p/2);
  LL halfhalf = (half * half)%MOD;

  if (p % 2 == 0)
    return halfhalf;
  else
    return (halfhalf * base)%MOD;
}

/*
* If there is a duplicated gondola, return 0.
* If all gondolas are > n, return 1.
* Otherwise, find the position of one of the original gondola, let this be idxOfOriginalGondola.
  Start from idxOfOriginalGondola, go around the circle and make sure all other original gondolas
  are in place.
*/
int valid(int n, int gondolas[]) {
  set<int> uniqGondolas;
  int idxOfOriginalGondola = -1;

  for (int i = 0; i < n; i++) {
    uniqGondolas.insert(gondolas[i]);
    if (gondolas[i] <= n) {
      idxOfOriginalGondola = i;
    }
  }

  if (uniqGondolas.size() < n) {
    return 0;
  }

  if (idxOfOriginalGondola == -1) {
    return 1;
  }

  for (int i = idxOfOriginalGondola, step = 0; step < n; i = (i + 1)%n, step++) {
    if (gondolas[i] <= n && gondolas[i] != (gondolas[idxOfOriginalGondola] - 1 + step)%n + 1) {
      return 0;
    }
  }

  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int id[n + 3];
  int oriIdx = -1;
  for (int i = 0; i < n; i++) {
    if (gondolaSeq[i] <= n) {
      oriIdx = i;
      break;
    }
  }

  if (oriIdx == -1) {
    for (int i = 0; i < n; i++) {
      id[i] = i + 1;
    }
  } else {
    for (int i = oriIdx, currentId = gondolaSeq[oriIdx], rep = 1; rep <= n; i = (i + 1)%n, rep++) {
      id[i] = currentId;
      currentId = (currentId == n ? 1 : currentId + 1);
    }
  }

  vector<pair<int, int> > newGondolasWithOriId;
  for (int i = 0; i < n; i++) {
    if (gondolaSeq[i] > n) {
      newGondolasWithOriId.push_back({gondolaSeq[i], id[i]});
    }
  }

  // Process from the smallest
  sort(newGondolasWithOriId.begin(), newGondolasWithOriId.end());

  int cntReplacement = 0;
  int lastGondola = n;
  for (auto [newGondola, oriId]: newGondolasWithOriId) {
    replacementSeq[cntReplacement++] = oriId;
    for (int g = lastGondola + 1; g < newGondola; g++) {
      replacementSeq[cntReplacement++] = g;
    }

    lastGondola = newGondola;
  }

  return cntReplacement;
}

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

int countReplacement(int n, int gondolas[]) {
  if (!valid(n, gondolas)) {
    return 0;
  }

  vector<int> largerThanN;
  for (int i = 0; i < n; i++) {
    if (gondolas[i] > n) {
      largerThanN.push_back(gondolas[i]);
    }
  }

  int cntReplaced = largerThanN.size();

  sort(largerThanN.begin(), largerThanN.end());

  vector<int> gapSizes;
  for (int i = 0; i < largerThanN.size(); i++) {
    int prev = (i == 0 ? n : largerThanN[i - 1]);
    int gapSize = largerThanN[i] - prev - 1;
    gapSizes.push_back(gapSize);
  }

  // cout << "cntReplaced: " << cntReplaced << endl;
  // cout << "gapSizes:"; for (auto gapSize: gapSizes) cout << " " << gapSize;
  // cout << endl;

  LL result = 1;
  for (int i = 0; i < gapSizes.size(); i++) {
    // cout << "hihi " << cntReplaced - i << " " << gapSizes[i] << endl;
    LL numWays = fastExponentiation(cntReplaced - i, gapSizes[i]);
    // cout << "numWays: " << numWays << endl;
    result = (result * numWays)%MOD;
  }

  if (cntReplaced == n) {
    result = (result * n)%MOD;
  }

  return result;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:38:27: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if (uniqGondolas.size() < n) {
      |       ~~~~~~~~~~~~~~~~~~~~^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0; i < largerThanN.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~
gondola.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int i = 0; i < gapSizes.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 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

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 17 ms 2148 KB Output is correct
7 Correct 26 ms 3668 KB Output is correct
8 Correct 27 ms 3908 KB Output is correct
9 Correct 8 ms 1492 KB Output is correct
10 Correct 26 ms 4448 KB Output is correct

Subtask #3
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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 10 ms 2132 KB Output is correct
7 Correct 27 ms 3668 KB Output is correct
8 Correct 22 ms 3924 KB Output is correct
9 Correct 11 ms 1360 KB Output is correct
10 Correct 23 ms 4436 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 11 ms 2004 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 31 ms 4636 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 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 7 ms 880 KB Output is correct
12 Correct 8 ms 980 KB Output is correct
13 Correct 18 ms 1292 KB Output is correct
14 Correct 9 ms 828 KB Output is correct
15 Correct 19 ms 2248 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 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 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 1 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 33 ms 3924 KB Output is correct
10 Correct 33 ms 3272 KB Output is correct
11 Correct 10 ms 1396 KB Output is correct
12 Correct 11 ms 1620 KB Output is correct
13 Correct 4 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 1 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 1 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 34 ms 4000 KB Output is correct
10 Correct 24 ms 3392 KB Output is correct
11 Correct 9 ms 1364 KB Output is correct
12 Correct 14 ms 1604 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 49 ms 4548 KB Output is correct
15 Correct 49 ms 5008 KB Output is correct
16 Correct 8 ms 1108 KB Output is correct
17 Correct 28 ms 3476 KB Output is correct
18 Correct 16 ms 2020 KB Output is correct