Submission #584929

#TimeUsernameProblemLanguageResultExecution timeMemory
584929MazaalaiGondola (IOI14_gondola)C++17
75 / 100
20 ms2228 KiB
#include <bits/stdc++.h> #include "gondola.h" #define ALL(x) x.begin(),x.end() #define LLA(x) x.rbegin(),x.rend() #define pb push_back using namespace std; using PII = pair <int, int>; using ll = long long; int valid(int n, int nums[]) { int mini = 0; for (int i = 1; i < n; i++) if (nums[i] < nums[mini]) mini = i; int st = nums[mini]; vector <int> tmp; for (int i = 0; i < n; i++) { int j = (mini + i) % n; if (nums[j] == st+i) continue; if (nums[j] > n) tmp.pb(nums[j]); if (nums[j] <= n) return 0; } sort(ALL(tmp)); for (int i = 1; i < tmp.size(); i++) if (tmp[i] == tmp[i-1]) return 0; return 1; } int replacement(int n, int nums[], int res[]) { int mini = 0, cp[n]; for (int i = 0; i < n; i++) { if (nums[i] < nums[mini]) mini = i; } iota(cp, cp+n, 1); vector <PII> vals; if (nums[mini] <= n) mini = (mini - (nums[mini] - 1) + n) % n; else mini = 0; for (int i = 0; i < n; i++) { vals.pb({nums[(mini+i)%n], i}); } sort(ALL(vals)); int ptr = 0, num = n+1; for (auto [a, b] : vals) { while (cp[b] != a) { res[ptr++] = cp[b]; cp[b] = num++; } } return ptr; } const int MOD = 1e9 + 9; ll Pow(ll a, ll b) { ll res = 1; while(b > 0) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b /= 2; } return res; } int countReplacement(int n, int nums[]) { if (!valid(n, nums)) return 0; int mini = 0, cp[n]; for (int i = 0; i < n; i++) if (nums[i] < nums[mini]) mini = i; iota(cp, cp+n, 1); vector <PII> vals; if (nums[mini] <= n) mini = (mini - (nums[mini] - 1) + n) % n; else mini = 0; for (int i = 0; i < n; i++) if (cp[i] != nums[(mini+i)%n]) vals.pb({nums[(mini+i)%n], i}); sort(ALL(vals)); int num = n+1, sz = vals.size(); ll ans = 1; for (auto [a, b] : vals) { ans = ans * Pow(sz, a - num) % MOD; num = a+1; sz--; } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 1; i < tmp.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...