제출 #543625

#제출 시각아이디문제언어결과실행 시간메모리
543625Cookie197건물 4 (JOI20_building4)C++17
11 / 100
219 ms24220 KiB
// Cookie197 // the people who invented competitive programming must be ******* crazy // why am i still here suffering while i can do something else more valuable? // WHY??? #pragma GCC optimize("O4,unroll-loops,no-stack-protector") #pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,fma") #include<iostream> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<string> #include<iomanip> #include<math.h> #include<unordered_map> #include<numeric> #include<random> using namespace std; #define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long #define pii pair<int,int> #define pdd pair<double ,double> #define mp make_pair //#define mod 998244353 #define mod 1000000007 #define endl "\n" #define inf (ll)1e18 #define out(x) cout << #x << " = " << x <<endl; #define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl; #define outp(x) cout << #x << " first = " << x.first << " second = " << x.second << endl int a[1000006], b[1000006], arr[100006][2]; int n; //bool ok[1000005][2]; //int dpx[1000005][2], dpy[1000005][2]; //char pre[1000005][2]; pii dp[1000005][2]; void ch(int &x,int y,int z,int i,int j){ //if (y<0) y = 2e9; //if (z<0) z = 2e9; //x = min(x,min(y,z)); //if (y==z && y==2e9) return; //if (y<z) pre[i][j] = 'A'; //else pre[i][j] = 'B'; } signed main(){ Why_does_competitive_programming_even_exist; cin>>n; for (int i=1;i<=2*n;i++) cin>>a[i], arr[i][0] = a[i]; for (int i=1;i<=2*n;i++) cin>>b[i], arr[i][1] = b[i]; //ok[1][0] = ok[1][1] = true; dp[1][0] = mp(1,1), dp[1][1] = mp(0,0); for (int i=2;i<=n*2;i++) dp[i][0] = mp(2e9,-1); for (int i=2;i<=n*2;i++){ int x=2e9, y=2e9; if (a[i-1] <= a[i]) x = dp[i-1][0].first; if (b[i-1] <= a[i]) y = dp[i-1][1].first; dp[i][0].first = min(x,y) + 1; x = -2e9, y = -2e9; if (a[i-1] <= a[i]) x = dp[i-1][0].second; if (b[i-1] <= a[i]) y = dp[i-1][1].second; dp[i][0].second = max(x,y) + 1; x=2e9, y=2e9; if (a[i-1] <= b[i]) x = dp[i-1][0].first; if (b[i-1] <= b[i]) y = dp[i-1][1].first; dp[i][1].first = min(x,y); x = -2e9, y = -2e9; if (a[i-1] <= b[i]) x = dp[i-1][0].second; if (b[i-1] <= b[i]) y = dp[i-1][1].second; dp[i][1].second = max(x,y); //outp(dp[i][0]); outp(dp[i][1]); } int pos = -1, now = n; if (dp[n*2][0].first <= n && n <= dp[n*2][0].second) pos = 0; else if (dp[n*2][1].first <= n && n <= dp[n*2][1].second) pos = 1; if (pos == -1){ cout<<-1<<endl; return 0; } string ans = ""; for (int i=n*2;i>=1;i--){ ans += (pos==0 ? 'A' : 'B'); now -= (pos==0 ? 1 : 0); if (arr[i-1][0] <= arr[i][pos] && dp[i-1][0].first <= now && now <= dp[i-1][0].second) pos = 0; else if (arr[i-1][1] <= arr[i][pos] && dp[i-1][1].first <= now && now <= dp[i-1][1].second) pos = 1; } reverse(ans.begin(),ans.end()); cout<<ans<<endl; /*dpx[1][0] = 1; dpy[1][1] = 1; for (int i=1;i<2*n;i++){ if (ok[i][0] && a[i] <= a[i+1]){ ch(dpx[i+1][0], dpx[i][0] + 1, -(dpy[i][0] - 1), i+1, 0); ch(dpy[i+1][0], dpy[i][0] - 1, -(dpx[i][0] + 1), i+1, 0); ok[i+1][0] = true; } if (ok[i][1] && b[i] <= a[i+1]){ ch(dpx[i+1][0], dpx[i][1] + 1, -(dpy[i][1] - 1), i+1, 0); ch(dpy[i+1][0], dpy[i][1] - 1, -(dpx[i][1] + 1), i+1, 0); ok[i+1][0] = true; } if (ok[i][0] && a[i] <= b[i+1]){ ch(dpx[i+1][1], dpx[i][0] - 1, -(dpy[i][0] + 1), i+1, 1); ch(dpy[i+1][1], dpy[i][0] + 1, -(dpx[i][0] - 1), i+1, 1); ok[i+1][1] = true; } if (ok[i][1] && b[i] <= b[i+1]){ ch(dpx[i+1][1], dpx[i][1] - 1, -(dpy[i][1] + 1), i+1, 1); ch(dpy[i+1][1], dpy[i][1] + 1, -(dpx[i][1] - 1), i+1, 1); ok[i+1][1] = true; } } for (int i=1;i<=n*2;i++){ cout<<dpx[i][0]<<" "<<dpx[i][1]<<" "<<dpy[i][0]<<" "<<dpy[i][1]<<endl; } //return 0; if (ok[2*n][0] == false && ok[2*n][1] == false) { cout<<-1<<endl; return 0; } if (dpx[2*n][0] != 0 && dpx[2*n][1] != 0 && dpy[2*n][0] != 0 && dpy[2*n][1] != 0) { cout<<-1<<endl; return 0; } string ans = ""; int pos; if (ok[n][0]) ans += 'A', pos = 0; else ans += 'B', pos = 1; for (int i=2*n;i>=2;i--){ ans += pre[i][pos]; if (pre[i][pos]=='A') pos = 0; else pos = 1; } reverse(ans.begin(),ans.end()); cout<<ans<<endl;*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...