제출 #652267

#제출 시각아이디문제언어결과실행 시간메모리
652267alvinpiter곤돌라 (IOI14_gondola)C++17
75 / 100
45 ms5096 KiB
#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 duplicate, return 0. * If all numbers are > n, return 1. * idxMini -> index of minimum number. If I go around (n - 1) steps starting from idxMini and only consider numbers which is <= n: * These numbers must appear in increasing order * If a and b are two consecutive numbers, then the number of numbers > n in between them must be b - a - 1. */ int valid(int n, int inputSeq[]) { set<int> uniqNumbers; int idxMini = -1; for (int i = 0; i < n; i++) { // There is a duplicate if (uniqNumbers.find(inputSeq[i]) != uniqNumbers.end()) { return 0; } uniqNumbers.insert(inputSeq[i]); if (inputSeq[i] <= n) { if (idxMini == -1 || inputSeq[i] < inputSeq[idxMini]) { idxMini = i; } } } // All numbers are > n. if (idxMini == -1) { return 1; } int lastIdx = idxMini; int cntInBetween = 0; for (int i = (idxMini + 1)%n, step = 1; step <= n - 1; i = (i + 1)%n, step++) { if (inputSeq[i] <= n) { if (inputSeq[i] < inputSeq[lastIdx] || inputSeq[i] - inputSeq[lastIdx] - 1 != cntInBetween) { return 0; } lastIdx = i; cntInBetween = 0; } else { cntInBetween += 1; } } 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 inputSeq[]) { if (!valid(n, inputSeq)) { return 0; } vector<int> largerThanN; for (int i = 0; i < n; i++) { if (inputSeq[i] > n) { largerThanN.push_back(inputSeq[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; if (gapSize > 0) { gapSizes.push_back(gapSize); } } LL result = 1; for (int i = 0; i < gapSizes.size(); i++) { LL numWays = fastExponentiation(cntReplaced - i, gapSizes[i]); result = (result * numWays)%MOD; } if (cntReplaced == n) { // Multiply with n! for (int i = 1; i <= n; i++) { result = (result * i)%MOD; } } return result; }

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for (int i = 0; i < largerThanN.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~
gondola.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int i = 0; i < gapSizes.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...