Submission #38709

#TimeUsernameProblemLanguageResultExecution timeMemory
3870914kgGondola (IOI14_gondola)C++11
75 / 100
126 ms11772 KiB
#include "gondola.h" #include <map> #include <set> #define N 100000 #define MOD 1000000009 using namespace std; int n, g_num, replace_num[N], out_temp[N]; long long count_tot = 1; map<int, int> valid_w; set<int> check; bool valid_check(int x) { set<int>::iterator it = check.lower_bound(x); if (it == check.end() || *it != x) return false; return true; } int valid(int _n, int in[]) { bool g_check = false; n = _n; for (int i = 0; i < n; i++) { if (g_check) { g_num = g_num == n ? 1 : g_num + 1; } if (valid_check(in[i])) return 0; valid_w[in[i]] = i, check.insert(in[i]); if (in[i] <= n) { if (g_check && g_num != in[i]) return 0; else if (!g_check) { g_check = true, g_num = in[i]; } } } return 1; } int replacement(int _n, int in[], int out[]) { int out_len = 0, w, k = _n + 1; long long cnt = 0; if (!valid(_n, in)) return -1; for (int i = 0; i < n; i++) { g_num = g_num == n ? 1 : g_num + 1; replace_num[i] = g_num; if (in[i] > n) cnt++; } if (cnt == n) count_tot *= (long long)n; for (int i = 0; i < n; i++) { w = replace_num[i]; while (k <= in[i]) { if (!valid_check(k)) { out[out_len++] = w; w = k++; count_tot *= cnt, count_tot %= MOD; } else if (valid_w[k] == i) { out[out_len++] = w; w = k++, cnt--; } else { out[out_len++] = replace_num[valid_w[k]]; k++, cnt--; } } } return out_len; } int countReplacement(int _n, int in[]) { if (replacement(_n, in, out_temp) < 0) return 0; return (int)count_tot; }
#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...