fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define nn "\n"
  7. #define pi pair<int, int>
  8. #define fi first
  9. #define se second
  10. #define lb lower_bound
  11. #define ub upper_bound
  12. #define eb emplace_back
  13. #define pb push_back
  14. #define TASK " "
  15.  
  16. #define ms(a, x) memset(a, x, sizeof(a))
  17. #define all(a) a.begin(), a.end()
  18. #define All(a, n) a + 1, a + 1 + n
  19.  
  20. #define LOG 19
  21.  
  22. const int INF = 1e18;
  23. const int mod = 1e9+7;
  24. const int N = 2e5 + 5;
  25. int MOD = 998244353;
  26. int bit[200000];
  27.  
  28. struct node{
  29. 	int kc, u, hk;
  30. 	bool operator<(const node& other) const {
  31.         return kc > other.kc;
  32.     }
  33. };
  34.  
  35. struct edge{
  36. 	int u, v, w;
  37. 	friend bool operator < ( edge a, edge b){
  38. 		return a.w < b.w;
  39. 	}
  40. };
  41.  
  42. void nhap(){
  43.  
  44. }
  45.  
  46. void solve(){
  47.     int n; cin >> n;
  48.     vector<int> a(n + 5);
  49.     int cnt1 = 0;
  50.     vector<int> pos, pos1;
  51.     for(int i = 1; i <= n; i++){
  52.         cin >> a[i];
  53.         if(a[i] == 1) pos.pb(i);
  54.         if(a[i] == -1) pos1.pb(i);
  55.     }
  56.     int best = 0;
  57.     int c = -1;
  58.     int l = -1, r = -1;
  59.     if(pos1.size() >= 2){
  60.         int k = pos1.back() - pos1.front() + 1;
  61.         if(k > best){
  62.             best = k;
  63.             c = 1;
  64.             l = pos1.front();
  65.             r = pos1.back();
  66.         }
  67.     }
  68.     if(!pos.empty() && !pos1.empty()){
  69.         for(int p : pos){
  70.             auto it = lb(all(pos1), p);
  71.             if(it != pos1.begin()){
  72.                 int prev_neg = *prev(it);
  73.                 int k = p - prev_neg + 1;
  74.                 if(k > best){
  75.                     best = k;
  76.                     c = 2;
  77.                     l = prev_neg;
  78.                     r = p;
  79.                 }
  80.             }
  81.             if(it != pos1.end()){
  82.                 int next_neg = *it;
  83.                 int k = next_neg - p + 1;
  84.                 if(k > best){
  85.                     best = k;
  86.                     c = 2;
  87.                     l = p;
  88.                     r = next_neg;
  89.                 }
  90.             }
  91.         }
  92.     }
  93.     if(pos.size() >= 2){
  94.         for(size_t i = 1; i < pos.size(); i++) {
  95.             int k = pos[i] - pos[i - 1] + 1;
  96.             if (k > best) {
  97.                 best = k;
  98.                 c = 3;
  99.                 l = pos[i - 1];
  100.                 r = pos[i];
  101.             }
  102.         }
  103.     }
  104.     vector<int> ans = a;
  105.     if(c == 1 || c == 2){
  106.         ans[l] = 1;
  107.         ans[r] = 1;
  108.     }
  109.     for(int i = 1; i <= n; i++){
  110.         if(ans[i] == -1) ans[i] = 0;
  111.     }
  112.     for(int i = 1; i <= n; i++){
  113.         cout << ans[i] << (i == n ? "" : " ");
  114.     }
  115.     cout << nn;
  116. }
  117.  
  118. signed main() {
  119. 	ios_base::sync_with_stdio(0);
  120. 	cin.tie(0);
  121. 	cout.tie(0);
  122.     int t;
  123.     cin >> t;
  124.     while(t--){
  125.         solve();
  126.     }
  127. 	return 0;
  128. }
Success #stdin #stdout 0s 5320KB
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
0
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
0 0 0
https://ideone.com/4fP9QL
language:
C++14 (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!