Submission #296611

#TimeUsernameProblemLanguageResultExecution timeMemory
296611emil_physmathGondola (IOI14_gondola)C++17
75 / 100
55 ms4856 KiB
#include "gondola.h" #include <numeric> #include <algorithm> #include <set> #include <vector> #include <iostream> using namespace std; using llong = long long; #define BUGO(x) cerr << #x << " = " << x << '\n'; int valid(int n, int a[]) { if (set<int>(a, a + n).size() != n) return false; set<int> ones; for (int i = 0; i < n; ++i) if (a[i] <= n) { int j = i - (a[i] - 1); if (j < 0) j += n; ones.insert(j); } return ones.size() <= 1; } //---------------------- int replacement(int n, int a[], int ans[]) { int anslen = 0; vector<int> must(n, -1); for (int i = 0; i < n; ++i) if (a[i] <= n) { for (int j = i; j < i + n; ++j) { must[j % n] = (a[i] + j - i) % n; if (!must[j % n]) must[j % n] = n; } break; } if (must[0] == -1) iota(must.begin(), must.end(), 1); vector<int> inds; inds.reserve(n); for (int i = 0; i < n; ++i) if (a[i] > n) inds.push_back(i); auto comp = [&a](int l, int r) { return a[l] < a[r]; }; sort(inds.begin(), inds.end(), comp); int gondol = n + 1; for (int i: inds) while (must[i] < a[i]) { ans[anslen++] = must[i]; must[i] = gondol++; } return anslen; } //---------------------- const llong mod = 1000'000'009LL; llong binpow(llong a, llong p) { if (p == 0) return 1; if (p % 2) return (a * binpow(a, p - 1)) % mod; return binpow((a * a) % mod, p / 2); } int countReplacement(int n, int a[]) { if (!valid(n, a)) return 0; vector<int> b; b.reserve(n); for (int i = 0; i < n; ++i) if (a[i] > n) b.push_back(a[i]); b.push_back(n); sort(b.begin(), b.end()); llong ans = 1; for (int i = 0; i + 1 < b.size(); ++i) { ans *= binpow((llong)b.size() - 1LL - i, b[i + 1] - b[i] - 1LL); ans %= mod; } if (*min_element(a, a + n) > n) { for (int i = 1; i <= n; ++i) { ans *= i; ans %= mod; } } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:13:35: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     if (set<int>(a, a + n).size() != n) return false;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i + 1 < b.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...