fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void solve(int n, vector<int>& a) {
  8.     vector<int> vec1;
  9.     for (int i = 0; i < n; i++) {
  10.         if (a[i] == 1) {
  11.             vec1.push_back(i);
  12.         }
  13.     }
  14.  
  15.     int bestLen = 0;
  16.     int bestL = -1, bestR = -1;
  17.  
  18.     // Check if at least a single 1 is possible (score >= 1)
  19.     for (int i = 0; i < n; i++) {
  20.         if (a[i] != 0) {
  21.             bestLen = 1;
  22.             bestL = i;
  23.             bestR = i;
  24.             break;
  25.         }
  26.     }
  27.  
  28.     auto update = [&](int l, int r) {
  29.         if (l != -1 && r != -1 && l < r) {
  30.             int len = r - l + 1;
  31.             if (len > bestLen) {
  32.                 bestLen = len;
  33.                 bestL = l;
  34.                 bestR = r;
  35.             }
  36.         }
  37.     };
  38.  
  39.     if (vec1.empty()) {
  40.         int first = -1, last = -1;
  41.         for (int i = 0; i < n; i++) {
  42.             if (a[i] != 0) {
  43.                 if (first == -1) first = i;
  44.                 last = i;
  45.             }
  46.         }
  47.         update(first, last);
  48.     } else {
  49.         for (size_t i = 0; i + 1 < vec1.size(); i++) {
  50.             update(vec1[i], vec1[i + 1]);
  51.         }
  52.  
  53.         int first_avail = -1;
  54.         for (int i = 0; i < vec1[0]; i++) {
  55.             if (a[i] != 0) {
  56.                 first_avail = i;
  57.                 break;
  58.             }
  59.         }
  60.         update(first_avail, vec1[0]);
  61.  
  62.         int last_avail = -1;
  63.         for (int i = n - 1; i > vec1.back(); i--) {
  64.             if (a[i] != 0) {
  65.                 last_avail = i;
  66.                 break;
  67.             }
  68.         }
  69.         update(vec1.back(), last_avail);
  70.     }
  71.  
  72.     if (bestL != -1) a[bestL] = 1;
  73.     if (bestR != -1) a[bestR] = 1;
  74.  
  75.     for (int i = 0; i < n; i++) {
  76.         if (a[i] == -1) {
  77.             a[i] = 0;
  78.         }
  79.     }
  80.  
  81.     for (int i = 0; i < n; i++) {
  82.         cout << a[i] << (i + 1 == n ? "" : " ");
  83.     }
  84.     cout << '\n';
  85. }
  86.  
  87. int main() {
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.  
  91.     int T;
  92.     cin >> T;
  93.  
  94.     while (T--) {
  95.         int n;
  96.         cin >> n;
  97.  
  98.         vector<int> a(n);
  99.         for (auto &x : a)
  100.             cin >> x;
  101.  
  102.         solve(n, a);
  103.     }
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
10
6
1 0 -1 0 0 1
7
0 -1 0 0 1 0 1
5
-1 0 0 -1 0
4
0 0 0 0
1
-1
6
1 0 1 0 0 -1
7
0 1 0 0 0 1 0
6
-1 -1 -1 -1 -1 -1
7
-1 0 1 -1 0 0 1
3
-1 0 0
stdout
copy 
1 0 0 0 0 1
0 1 0 0 1 0 1
1 0 0 1 0
0 0 0 0
1
1 0 1 0 0 1
0 1 0 0 0 1 0
1 0 0 0 0 1
0 0 1 0 0 0 1
1 0 0
https://ideone.com/xLd31u
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!