제출 #211806

#제출 시각아이디문제언어결과실행 시간메모리
211806username건물 4 (JOI20_building4)C++14
100 / 100
352 ms52076 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/rope> using namespace __gnu_pbds; using namespace __gnu_cxx; #define tr(it,a) for(auto it:a) #define pob pop_back #define pf push_front #define pof pop_front #define umin(x,y) (x=min(x,(y))) #define umax(x,y) (x=max(x,(y))) #define mid ((l+r)/2) #define lch (idx*2+1) #define rch (idx*2+2) // #include<bits/stdc++.h> #define int int_fast64_t using namespace std; typedef pair<int,int> pii; #define REP(i,j,k) for(int i=(j);i<(k);++i) #define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i) #define ALL(a) a.begin(),a.end() #define pb push_back #define f first #define s second #define endl '\n' // #define __db #ifdef __db #define IOS #define prt(...) cerr<<__VA_ARGS__ #define ary(s,t)\ for(auto it=(s);it!=(t);++it)prt(*it<<" ");\ prt(endl); #else #define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false) #define prt(...) #define ary(...) #endif // const int maxn=1e6+9,inf=1ll<<60; int n,m,a[maxn][2]; pii dp[maxn][2]; string s; pii merge(pii x,pii y){ if(x.f<0)return y; else if(y.f<0)return x; else return {min(x.f,y.f),max(x.s,y.s)}; } main(){ IOS; cin>>n,m=n<<1; REP(i,0,2)REP(j,0,m)cin>>a[j][i]; dp[0][0]={0,0}; dp[0][1]={1,1}; REP(i,1,m){ REP(j,0,2){ dp[i][j]={-inf,-inf}; if(a[i-1][0]<=a[i][j]){ pii tt=dp[i-1][0]; tt.f+=j,tt.s+=j; dp[i][j]=merge(dp[i][j],tt); } if(a[i-1][1]<=a[i][j]){ pii tt=dp[i-1][1]; tt.f+=j,tt.s+=j; dp[i][j]=merge(dp[i][j],tt); } } } pii tt={m-1,0},x=dp[tt.f][tt.s]; if(n<x.f||x.s<n){ tt.s=1,x=dp[tt.f][tt.s]; if(n<x.f||x.s<n)return cout<<-1<<endl,0; } s+='A'+tt.s; int c=n-tt.s; while(tt.f){ REP(i,0,2){ if(a[tt.f-1][i]<=a[tt.f][tt.s]&&dp[tt.f-1][i].f<=c&&c<=dp[tt.f-1][i].s){ tt={tt.f-1,i}; c-=i; break; } } s+='A'+tt.s; } reverse(ALL(s)); cout<<s<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

building4.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...