Submission #89375

#TimeUsernameProblemLanguageResultExecution timeMemory
89375vexPoklon (COCI17_poklon7)C++14
120 / 120
385 ms56464 KiB
#include <bits/stdc++.h> #define maxn 1000005 #define pll_i pair<long long,int> #define broj first #define ste2 second using namespace std; int n; int l[maxn]; int r[maxn]; pll_i veci(pll_i a,pll_i b) { if(a.broj<b.broj) { swap(a.broj,b.broj); swap(a.ste2,b.ste2); } int lg2_a=0,lg2_b=0; long long abr=a.broj; long long bbr=b.broj; while(abr>0LL) { lg2_a++; abr/=2; } while(bbr>0LL) { lg2_b++; bbr/=2; } bbr=b.broj; int ste2_b=b.ste2; while(lg2_b<lg2_a) { lg2_b++; bbr*=2; ste2_b--; } if(ste2_b>a.ste2)return b; if(ste2_b<a.ste2)return a; if(bbr>a.broj)return b; return a; } pll_i resi(int x) { pll_i res1,res2; if(l[x]>0)res1=resi(l[x]);else res1={-l[x],0}; if(r[x]>0)res2=resi(r[x]);else res2={-r[x],0}; pll_i sol=veci(res1,res2); sol.ste2++; //cout<<res1.broj<<","<<res1.ste2<<" "<<res2.broj<<","<<res2.ste2<<" "<<sol.broj<<","<<sol.ste2<<endl; return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; for(int i=1;i<=n;i++) { cin>>l[i]>>r[i]; } pll_i sol=resi(1); //cout<<sol.broj<<" "<<sol.ste2<<endl; string s; while(sol.broj>0) { s.push_back(sol.broj%2 + '0'); sol.broj/=2; } int len=s.size(); for(int i=len-1;i>=0;i--)cout<<s[i]; while(sol.ste2>0) { cout<<"0"; sol.ste2--; } /*string s; while(sol>0) { s.push_back(sol%2 + '0'); sol/=2; } int len=s.size(); for(int i=len-1;i>=0;i--)cout<<s[i];*/ return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...