Submission #754737

#TimeUsernameProblemLanguageResultExecution timeMemory
754737Sam_a17Gondola (IOI14_gondola)C++17
100 / 100
66 ms7248 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> // #include <rail.h> #include "gondola.h" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define pb push_back #define popf pop_front #define popb pop_back #define ld long double #define ll long long void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} void print(long double t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; long long ka() { long long x = 0; bool z = false; while (1) { char y = getchar(); if (y == '-') z = true; else if ('0' <= y && y <= '9') x = x * 10 + y - '0'; else { if (z) x *= -1; return x; } } } // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } else if(str == "input") { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const long long mod = 1000000009; const int N = 4e6 + 10; int cnt[N], cnt2[N]; int valid(int n, int inputSeq[]) { for(int i = 0; i < n; i++) { cnt[inputSeq[i]]++; if(cnt[inputSeq[i]] > 1) { return 0; } } for(int i = 0; i < n; i++) { if(inputSeq[i] <= n) { int lef = inputSeq[i] - 1; if(lef == 0) lef = n; int li = (i - 1 + n) % n; if(inputSeq[li] <= n && inputSeq[li] != lef) { return 0; } int rig = inputSeq[i] + 1; if(rig > n) { rig = 1; } int ri = (i + 1) % n; if(inputSeq[ri] <= n && inputSeq[ri] != rig) { return 0; } } } return 1; } int valid2(int n, vector<int> inputSeq) { map<int, int> mpi; for(int i = 0; i < n; i++) { mpi[inputSeq[i]]++; if(mpi[inputSeq[i]] > 1) { return 0; } } for(int i = 0; i < n; i++) { if(inputSeq[i] <= n) { int lef = inputSeq[i] - 1; if(lef == 0) lef = n; int li = (i - 1 + n) % n; if(inputSeq[li] <= n && inputSeq[li] != lef) { return 0; } int rig = inputSeq[i] + 1; if(rig > n) { rig = 1; } int ri = (i + 1) % n; if(inputSeq[ri] <= n && inputSeq[ri] != rig) { return 0; } } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { set<pair<int, int>> st; int mx = 0; int ok = 0; vector<int> which(n); for(int i = 0; i < n; i++) { if(gondolaSeq[i] > n) { mx = max(mx, gondolaSeq[i]); st.insert({gondolaSeq[i], i}); } else if(!ok) { int j = i, it = gondolaSeq[i]; for(int k = 0; k < n; k++) { which[j] = it; it++; if(it == n + 1) { it = 1; } j++; j %= n; } ok = 1; } } if(!ok) { for(int i = 0; i < n; i++) { which[i] = (i + 1); } } int bit = 0; for(int i = n + 1; i <= mx; i++) { if(st.begin()->first == i) { replacementSeq[bit] = which[st.begin()->second]; st.erase(st.begin()); } else { auto it = st.rbegin()->second; replacementSeq[bit] = which[it]; which[it] = i; } bit++; } assert(sz(st) == 0); return bit; } long long add(long long a, long long b) { return (a + b) % mod; } long long mult(long long a, long long b) { return (a * b) % mod; } long long sub(long long a, long long b) { return (a - b + 2 * mod) % mod; } long long binPowByMod(long long a, long long b) { a %= mod; long long res = 1; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int countReplacement(int n, int inputSeq[]) { vector<int> veci; for(int i = 0; i < n; i++) { veci.push_back(inputSeq[i]); } if(!valid2(n, veci)) { return 0; } vector<pair<long long, long long>> st; long long mx = 0; for(int i = 0; i < n; i++) { if(inputSeq[i] > n) { mx = max(mx, (long long)inputSeq[i]); st.push_back({inputSeq[i], i}); } } long long ct = sz(st); long long answ = 1; if(ct == n) { answ = mult(answ, n); } sort(all(st)); if(sz(st)) { if(st[0].first != n + 1) { answ = mult(answ, binPowByMod(ct, st[0].first - (n + 1))); } ct--; for(int i = 1; i < sz(st); i++) { long long val = st[i].first - st[i - 1].first - 1; answ = mult(answ, binPowByMod(ct, val)); ct--; } } return answ; }

Compilation message (stderr)

gondola.cpp: In function 'void setIO(std::string)':
gondola.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gondola.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gondola.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
gondola.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...