제출 #370242

#제출 시각아이디문제언어결과실행 시간메모리
370242stoyan_malinin건물 4 (JOI20_building4)C++14
0 / 100
22 ms17132 KiB
#include <functional> #include <iostream> #include <cstring> #include <vector> #include <deque> using namespace std; const int MAXN = 1e6 + 5; int n; int a[MAXN][2]; namespace MaxA { int memo[MAXN][2]; int rec(int ind, int lastChoice) { if(ind==n) return 0; if(memo[ind][lastChoice]!=-1) return memo[ind][lastChoice]; int ans = -MAXN; int lastVal = ((ind==0)?-1:a[ind-1][lastChoice]); for(int c = 0;c<2;c++) { if(lastVal<=a[ind][c]) ans = max(ans, (c==0) + rec(ind+1, c)); } memo[ind][lastChoice] = ans; return ans; } vector <int> solve() { memset(memo, -1, sizeof(memo)); vector <int> ans = {}; int aCnt = rec(0, 0), lastVal = -1; if(aCnt<0) { cout << "-1" << '\n'; exit(0); } for(int i = 0;i<n;i++) { for(int c = 0;c<2;c++) { if(lastVal<=a[i][c] && (c==0) + rec(i+1, c)==aCnt) { ans.push_back(c); aCnt -= (c==0); lastVal = a[i][c]; break; } } } return ans; } } int comp[MAXN]; pair <int, int> maxB[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n;n *= 2; for(int i = 0;i<n;i++) cin >> a[i][0]; for(int i = 0;i<n;i++) cin >> a[i][1]; for(int i = 0;i<n-1;i++) { if(min(a[i][0], a[i][1])>max(a[i+1][0], a[i+1][1])) { cout << "-1" << '\n'; return 0; } } comp[0] = 0; for(int i = 1;i<n;i++) { if(a[i-1][1]<=a[i][1]) comp[i] = comp[i-1]; else comp[i] = i; } int aCnt = 0; vector <int> s = MaxA::solve(); for(int i = 0;i<n;i++) aCnt += (s[i]==0); if(aCnt<n/2) { cout << "-1" << '\n'; return 0; } int lastB = -1; deque <int> dq; for(int i = 0;i<n;i++) { if(s[i]==1) lastB = i; maxB[i] = {0, 0}; if(i!=0) maxB[i] = max(maxB[i], make_pair(maxB[i-1].first, 0)); while(dq.empty()==false && (dq.back()<=lastB || comp[dq.back()]!=comp[i])) dq.pop_back(); if(s[i]==0 && (i==0 || a[i-1][s[i-1]]<=a[i][1])) { while(dq.empty()==false) { int val1 = ((dq.front()-2>=0)?maxB[dq.front()-2].first:0) + (i-dq.front()+1); int val2 = ((i-2>=0)?maxB[i-2].first:0) + (i-i+1); if(val1<val2) dq.pop_front(); else break; } dq.push_front(i); } if(i==n-1 || a[i][1]<=a[i+1][s[i+1]]) { if(dq.empty()==false) { int j = dq.back(); int val = ((j-2>=0)?maxB[j-2].first:0); maxB[i] = max(maxB[i], make_pair(val+(i-j+1), (i-j+1))); } for(int j = 0;j<=min(2, i);j++) { if(j<=lastB) continue; if(j!=i && comp[i]!=comp[j]) continue; if(j==0 || a[j-1][s[j-1]]<=a[j][1]) { int val = ((j-2>=0)?maxB[j-2].first:0); maxB[i] = max(maxB[i], make_pair(val+(i-j+1), (i-j+1))); } } } //cout << maxB[i].first << " " << maxB[i].second << '\n'; } int ind = -1; int toCompensate = aCnt - n/2; for(int i = 0;i<n;i++) { //cout << maxB[i].first << " " << maxB[i].second << '\n'; if(maxB[i].first>=toCompensate) { ind = i; break; } } //if(maxB[n-1].first>=toCompensate) ind = n - 1; if(ind==-1) { if(n>2000) cout << 1/0 << '\n'; cout << "-1" << '\n'; return 0; } while(toCompensate>0) { if(ind<0) { cout << 1/0 << '\n'; return 0; } if(maxB[ind].second<=toCompensate) { toCompensate -= maxB[ind].second; for(int i = ind-maxB[ind].second+1;i<=ind;i++) s[i] = 1; ind = ind - maxB[ind].second - 1; } else { //cout << "OK " << ind << '\n'; int l = ind - maxB[ind].second + 1; int r = ind; bool found = false; for(int i = l;i<=r;i++) { if(l==0 || a[l-1][s[l-1]]<=a[l][1]) { if(i==n-1 || a[i][1]<=a[i+1][s[i+1]]) { if(i-l+1==toCompensate) { for(int j = l;j<=i;j++) { s[j] = 1; } found = true; break; } } } if(r==n-1 || a[r][1]<=a[r+1][s[r+1]]) { if(i==0 || a[i-1][s[i-1]]<=a[i][1]) { if(r-i+1==toCompensate) { for(int j = i;j<=r;j++) { s[j] = 1; } found = true; break; } } } } if(found==false) { cout << 1/0 << '\n'; } break; } } int lastVal = -1; if(s.size()!=n) { cout << 1/0 << '\n'; } int balance = 0; for(int i = 0;i<s.size();i++) { if(s[i]==0) balance += 1; else balance += -1; } if(balance!=0) { cout << 1/0 << '\n'; } for(int i = 0;i<s.size();i++) { if(lastVal>a[i][s[i]]) { cout << 1/0 << '\n'; return 0; } lastVal = a[i][s[i]]; } for(int x: s) cout << char('A'+x); cout << '\n'; }

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

building4.cpp: In function 'int main()':
building4.cpp:177:29: warning: division by zero [-Wdiv-by-zero]
  177 |         if(n>2000) cout << 1/0 << '\n';
      |                            ~^~
building4.cpp:187:22: warning: division by zero [-Wdiv-by-zero]
  187 |             cout << 1/0 << '\n';
      |                     ~^~
building4.cpp:246:26: warning: division by zero [-Wdiv-by-zero]
  246 |                 cout << 1/0 << '\n';
      |                         ~^~
building4.cpp:254:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  254 |     if(s.size()!=n)
      |        ~~~~~~~~^~~
building4.cpp:256:18: warning: division by zero [-Wdiv-by-zero]
  256 |         cout << 1/0 << '\n';
      |                 ~^~
building4.cpp:260:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |     for(int i = 0;i<s.size();i++)
      |                   ~^~~~~~~~~
building4.cpp:268:18: warning: division by zero [-Wdiv-by-zero]
  268 |         cout << 1/0 << '\n';
      |                 ~^~
building4.cpp:271:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |     for(int i = 0;i<s.size();i++)
      |                   ~^~~~~~~~~
building4.cpp:275:22: warning: division by zero [-Wdiv-by-zero]
  275 |             cout << 1/0 << '\n';
      |                     ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...