Submission #867482

#TimeUsernameProblemLanguageResultExecution timeMemory
867482andrej246Zalmoxis (BOI18_zalmoxis)C++14
0 / 100
199 ms74040 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i,N) for(long long i = 0; (i) < (N); (i)++) #define FORS(i,v,N) for(long long i = v; (i) < (N); (i)++) #define FORI(i,v,N,inc) for(long long i = v; (i) < (N); (i)+=(inc)) #define NL '\n' #define EL cout << NL #define PRINTV(v) for(auto a:(v)) {cout << a << " ";};EL #define PRINTVV(v) for(auto a:(v)) {PRINTV(a);} #define STRP(p) "{" << (p).first << "," << (p).second << "}" #define PRINTVP(v) for(auto a:(v)) {cout << STRP(a) << " ";};EL #define PRINTVV(v) for(auto a:(v)) {PRINTV(a);} typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef pair<ll,ll> pl; typedef vector<pl> vpl; typedef vector<vpl> vvpl; vl partsplit(ll num, ll t) { vl res; ll pow = 1; ll val = num-1; while (t) { if (t % 2) { FOR(_,pow) { res.push_back(val); } } t /= 2; pow *= 2; val --; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); ll N,K; cin >> N >> K; vl s(N); FOR(i,N) cin >> s[i]; vvl changes(N); vl index(N); vl cur_s = s; ll cur_n = N; ll new_len = N; FOR(i,N) { index[i] = i; } FOR(x,30) { bool prev = false; vl next_s; vl next_index; ll next_n = 0; ll cur_index = 0; FOR(i,cur_n) { if (cur_s[i] == x) { if (prev == false) prev = true; else { prev = false; next_s.push_back(x+1); next_n++; next_index.push_back(cur_index); cur_index++; } } else { if (prev == true) { changes[index[i-1]].push_back(x); new_len++; prev = false; next_s.push_back(x+1); next_n++; next_index.push_back(cur_index); cur_index++; } next_s.push_back(cur_s[i]); next_index.push_back(cur_index); cur_index++; next_n++; } } if (prev == true) { changes[index[cur_n-1]].push_back(x); new_len++; prev = false; next_s.push_back(x+1); next_n++; next_index.push_back(cur_index); cur_index++; } cur_s = next_s; index = next_index; cur_n = next_n; //PRINTV(cur_s); //PRINTV(index); //PRINTVP(changes); } vl new_s; ll target = N + K - new_len; assert(target >= 0); FOR(i,N) { new_s.push_back(s[i]); for (auto x:changes[i]) { if (target == 0) new_s.push_back(x); else if (target >= pow(2,x)-1) { FOR(_,pow(2,x)) { new_s.push_back(0); } target -= pow(2,x)-1; } else { vl part = partsplit(x,target+1); for (auto v: part) { new_s.push_back(v); } target = 0; } } } PRINTV(new_s); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...