제출 #320782

#제출 시각아이디문제언어결과실행 시간메모리
320782aZvezda건물 4 (JOI20_building4)C++14
11 / 100
120 ms105964 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e9 + 7; #define out(x) "{" << (#x) << ": " << x << "} " const int MAX_N = 4e3 + 10; int n, a[MAX_N], b[MAX_N]; int dp[MAX_N][MAX_N][2]; bool hist[MAX_N][MAX_N][2]; void output(int x, int y, int last) { if(x == -1) {return;} output(x - 1, y - last, hist[x][y][last]); if(last) { cout << "B"; } else { cout << "A"; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; n *= 2; for(int i = 0; i < n; i ++) { cin >> a[i]; } for(int i = 0; i < n; i ++) { cin >> b[i]; } dp[0][0][0] = 1; dp[0][1][1] = 1; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { if(dp[i][j][0]) { int now = a[i]; if(now <= a[i + 1]) { dp[i + 1][j][0] = 1; hist[i + 1][j][0] = 0; } if(now <= b[i + 1]) { dp[i + 1][j + 1][1] = 1; hist[i + 1][j + 1][1] = 0; } } if(dp[i][j][1]) { int now = b[i]; if(now <= a[i + 1]) { dp[i + 1][j][0] = 1; hist[i + 1][j][0] = 1; } if(now <= b[i + 1]) { dp[i + 1][j + 1][1] = 1; hist[i + 1][j + 1][1] = 1; } } } } if(!dp[n - 1][n / 2][0] && !dp[n - 1][n / 2][1]) { cout << -1 << endl; } else if(dp[n - 1][n / 2][1]) { output(n - 1, n / 2, 1); } else { output(n - 1, n / 2, 0); } return 0; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { cout << dp[i][j][0] << " "; } cout << endl; } cout << endl; for(int i = 0; i < n; i ++) { for(int j = 0; j < n; j ++) { cout << dp[i][j][1] << " "; } cout << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...