제출 #1096543

#제출 시각아이디문제언어결과실행 시간메모리
1096543Tymond곤돌라 (IOI14_gondola)C++17
20 / 100
30 ms6600 KiB
#include <bits/stdc++.h> #include "gondola.h" using namespace std; using ll = long long; using ld = long double; #define fi first #define se second #define vi vector<int> #define vll vector<long long> #define pii pair<int, int> #define pll pair<long long, long long> #define pb push_back #define mp make_pair #define eb emplace_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count()); inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);} inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);} #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; int valid(int n, int inputSeq[]){ vi a; vi vec; map<int, int> cnt; pii mn = {10000000, 0}; for(int i = 0; i < n; i++){ a.pb(inputSeq[i]); cnt[a[i]]++; if(a[i] < mn.fi){ mn.fi = a[i]; mn.se = i; } } for(auto ele : cnt){ if(ele.se > 1){ return 0; } } vi na; for(int i = mn.se; i < n; i++){ na.pb(a[i]); } for(int i = 0; i < mn.se; i++){ na.pb(a[i]); } a = na; for(int i = 0; i < n; i++){ if(a[i] <= n){ vec.pb(i); } } if(sz(vec) <= 1){ return 1; } for(int i = 0; i + 1 < sz(vec); i++){ if(a[vec[i + 1]] <= a[vec[i]]){ return 0; } if(vec[i + 1] - vec[i] != a[vec[i + 1]] - a[vec[i]]){ return 0; } } if(n - vec.back() - 1 != (n - a[vec.back()] + a[vec[0]] - 1)){ return 0; } return 1; } //---------------------- const int INF = 1e9; int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int l = 0; vi a; set<pii> x; pii mn = {INF, 0}; for(int i = 0; i < n; i++){ a.pb(gondolaSeq[i]); if(a[i] > n){ x.insert({a[i], i}); } if(a[i] < mn.fi){ mn.fi = a[i]; mn.se = i; } } vi p; int ok = n + 1; while(sz(x)){ pii akt = *(x.begin()); x.erase(x.begin()); int our = (mn.fi > n ? akt.se + 1 : (mn.se <= akt.se ? akt.se -mn.se + 1 : n - mn.se + akt.se + 1)); p.pb(our); our = ok; while(our < akt.fi){ p.pb(our); our++; } ok = our + 1; } l = sz(p); for(int i = 0; i < l; i++){ replacementSeq[i] = p[i]; } return l; } //---------------------- int countReplacement(int n, int inputSeq[]){ return -3; } /*int main(){ int S[7] = {2, 3, 4, 12, 6, 7, 1}; int R[10]; cout<<replacement(7, S,R) << '\n'; for(auto ele : R){ cout << ele << ' '; } cout << '\n'; }*/
#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...