oj.uz

답안 #652285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652285 2022-10-22T02:16:56 Z alvinpiter 곤돌라 (IOI14_gondola) C++17
100 / 100
 44 ms 5096 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;
}

/*
* For each of the given gondola, find the original gondola that it replaces. Here's how:
  - If there is an original gondola, then just go around the circle starting from it.
  - If there is no original gondola, then we assume the original gondolas were ordered from 1 to n.
* Process the new gondolas starting from the smallest-numbered one. For example, there is a gondola numbered
  10 which replaces gondola 4. Then the replacement sequence will be:
  4 -> <lastUsedGondola + 1> -> <lastUsedGondola + 2> -> ... -> 9

  lastUsedGondola initially equals to n, and updated accordingly.
*/
int replacement(int n, int gondolas[], int replacementSeq[])
{
  int idxOfOriginalGondola = -1;
  for (int i = 0; i < n; i++) {
    if (gondolas[i] <= n) {
      idxOfOriginalGondola = i;
      break;
    }
  }

  vector<pair<int, int> > newGondolasWithOriginal;
  if (idxOfOriginalGondola == -1) {
    for (int i = 0; i < n; i++) {
      newGondolasWithOriginal.push_back({gondolas[i], i + 1});
    }
  } else {
    for (int i = idxOfOriginalGondola, step = 0; step < n; i = (i + 1)%n, step++) {
      if (gondolas[i] > n) {
        newGondolasWithOriginal.push_back({gondolas[i], (gondolas[idxOfOriginalGondola] - 1 + step)%n + 1});
      }
    }
  }

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

  int cntReplacement = 0;
  int lastUsedGondola = n;
  for (auto [newGondola, originalGondola]: newGondolasWithOriginal) {
    replacementSeq[cntReplacement++] = originalGondola;
    for (int g = lastUsedGondola + 1; g < newGondola; g++) {
      replacementSeq[cntReplacement++] = g;
    }

    lastUsedGondola = 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:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i = 0; i < largerThanN.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~
gondola.cpp:132:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i = 0; i < gapSizes.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 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 10 ms 2220 KB Output is correct
7 Correct 28 ms 3624 KB Output is correct
8 Correct 19 ms 3860 KB Output is correct
9 Correct 7 ms 1488 KB Output is correct
10 Correct 26 ms 4508 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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 11 ms 2148 KB Output is correct
7 Correct 27 ms 3580 KB Output is correct
8 Correct 20 ms 3924 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 26 ms 4436 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 13 ms 2088 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 31 ms 4592 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 308 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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
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 8 ms 852 KB Output is correct
12 Correct 9 ms 916 KB Output is correct
13 Correct 12 ms 1432 KB Output is correct
14 Correct 8 ms 816 KB Output is correct
15 Correct 18 ms 2252 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 38 ms 3924 KB Output is correct
10 Correct 29 ms 3284 KB Output is correct
11 Correct 9 ms 1440 KB Output is correct
12 Correct 12 ms 1620 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 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 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 41 ms 4004 KB Output is correct
10 Correct 29 ms 3356 KB Output is correct
11 Correct 10 ms 1364 KB Output is correct
12 Correct 11 ms 1624 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 38 ms 4436 KB Output is correct
15 Correct 44 ms 5096 KB Output is correct
16 Correct 7 ms 1236 KB Output is correct
17 Correct 33 ms 3536 KB Output is correct
18 Correct 15 ms 2132 KB Output is correct