Submission #430973

#TimeUsernameProblemLanguageResultExecution timeMemory
430973faresbasbsZalmoxis (BOI18_zalmoxis)C++14
10 / 100
461 ms262148 KiB
#include <bits/stdc++.h> using namespace std; vector<int> v[1000001]; int n,k,arr[1000001]; void solve(int l , int r , int val , int freq){ if(r == l-1){ for(int i = 0 ; i < freq ; i += 1){ v[r].push_back(val); } return ; } int pos = -1; for(int i = l ; i <= r ; i += 1){ if(arr[i] == val){ pos = i; break; } } if(pos == -1){ solve(l,r,val-1,2*freq); return ; } int farr[31]; memset(farr,0,sizeof farr); for(int i = l ; i < pos ; i += 1){ farr[arr[i]] += 1; } int tag = 0; for(int i = 0 ; i < val ; i += 1){ farr[i+1] += farr[i]/2; if(farr[i]%2 == 1){ tag = 1; } } freq -= 1; solve(l,pos-1,val,farr[val]+tag),solve(pos+1,r,val,freq-farr[val]-tag); } int main(){ cin >> n >> k; for(int i = 1 ; i <= n ; i += 1){ cin >> arr[i]; } solve(1,n,30,1); vector<int> varr; for(int i = 0 ; i <= n ; i += 1){ for(auto j : v[i]){ varr.push_back(j); } if(i){ varr.push_back(arr[i]); } } for(auto i : varr){ cout << i << " "; }cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...