제출 #1256471

#제출 시각아이디문제언어결과실행 시간메모리
1256471DangerNoodle7591Xylophone (JOI18_xylophone)C++20
0 / 100
2 ms2752 KiB
#include <bits/stdc++.h> using namespace std; //#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); //#define endl '\n' //#define int long long int #define ll long long #define NN 10000 #define carp 10000000 #define pb push_back #define p push #define ins insert #define f first #define s second int query(int s,int t); void answer(int i,int a); /*int query(int s,int t){ cout<<s<<" "<<t<<endl; int a;cin>>a; return a; } void answer(int i,int a){ cout<<i<<" "<<a<<endl; }*/ pair<vector<int>,vector<int>> arr[NN],seg[NN*4]; int deg[NN*4]; int val[NN]; void yap(int x,int b,int fark,int kim){ int okey_sol=0,okey_sag=0; if(seg[x].f.size()==0)okey_sol=1; if(seg[x].s.size()==0)okey_sag=1; if(seg[x].f.size()){ for(auto u:seg[x].f){ if(u<0||u>fark){okey_sol=1;break;} } } if(seg[x].s.size()){ for(auto u:seg[x].s){ if(u<0||u>fark){okey_sag=1;break;} } } if(kim==1){ if(okey_sol)seg[x].f=seg[x*2].f; if(okey_sag)seg[x].s=seg[x*2].s; } else{ if(okey_sol)seg[x].f=seg[x*2+1].f; if(okey_sag)seg[x].s=seg[x*2+1].s; if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end()); if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end()); reverse(seg[b].f.begin(),seg[b].f.end()); reverse(seg[b].s.begin(),seg[b].s.end()); } if(okey_sol){ set<int> st; int sonn=0; for(auto u:seg[x].f){ sonn=u; st.ins(u); } int ok=1,geld=1; int son=sonn; for(auto u:seg[b].f){ if(geld){ son-=u; geld=0;continue; } int yeni=u+son; if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){ ok=0;break; } } if(ok){ geld=1; for(auto u:seg[b].f){ if(geld){geld=0;continue;} seg[x].f.pb(u+son); } } else{ geld=1; for(auto u:seg[b].s){ if(geld){ sonn-=u; geld=0;continue; } seg[x].f.pb(u+sonn); } } } if(okey_sag){ set<int> st; int sonn=0; for(auto u:seg[x].s){ sonn=u; st.ins(u); } int ok=1,geld=1; int son=sonn; for(auto u:seg[b].f){ if(geld){ son-=u; geld=0;continue; } int yeni=u+son; if(st.find(yeni)!=st.end()||yeni<0||yeni>fark){ ok=0;break; } } if(ok){ geld=1; for(auto u:seg[b].f){ if(geld){geld=0;continue;} seg[x].s.pb(u+son); } } else{ geld=1; for(auto u:seg[b].s){ if(geld){ sonn-=u; geld=0;continue; } seg[x].s.pb(u+sonn); } } } if(kim!=1){ if(okey_sol)reverse(seg[x].f.begin(),seg[x].f.end()); if(okey_sag)reverse(seg[x].s.begin(),seg[x].s.end()); reverse(seg[b].f.begin(),seg[b].f.end()); reverse(seg[b].s.begin(),seg[b].s.end()); } } void bui(int x,int l,int r){ if(l>r)return; if(l==r){ seg[x]=arr[l]; deg[x]=val[l];return; } int mid=(l+r)/2; bui(x*2,l,mid);bui(x*2+1,mid+1,r); deg[x]=query(l,r+1); if(deg[x]!=deg[x*2+1])yap(x,x*2+1,deg[x],1); if(deg[x]!=deg[x*2]) yap(x,x*2,deg[x],0); /*cout<<x<<" "<<l<<" "<<r<<": "<<deg[x]<<endl; for(auto u:seg[x].f)cout<<u<<" "; cout<<endl; for(auto u:seg[x].s)cout<<u<<" "; cout<<endl<<endl; */ } void solve(int N){ for(int i=1;i<N;i++){ int de=query(i,i+1); arr[i]={{0,de},{de,0}}; val[i]=de; } bui(1,1,N-1); int okey=0; for(auto u:seg[1].f){ if(u==0){ okey=1;break; } if(u==N-1)break; } if(okey){ int i=1; for(auto u:seg[1].f){ answer(i,u+1); i++; } } else{ int i=1; for(auto u:seg[1].s){ answer(i,u+1); i++; } } } /*signed main(){ lalala; int n;cin>>n; solve(n); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...