fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  7. typedef long long ll;
  8.  
  9. int main() {
  10.     int t;
  11.     cin >> t;
  12.     while(t--){
  13.         ll n, find = 0, a = 0, b = 0, c = 0, d = 0, sa = 0, sb = 0, sc = 0, sd = 0;
  14.         cin >> n;
  15.         vector<int> v(n);
  16.         set <int> s;
  17.         for(int i = 0; i < n; i++){
  18.             cin >> v[i];
  19.             if(v[i] != 1 && v[i] != -1){
  20.                 find = i;
  21.             }
  22.         }
  23.         for(int i = 0; i < find; i++){
  24.             sa = max(0ll, sa + v[i]);
  25.             sb = min(0ll, sb + v[i]);
  26.             a = max(a, sa);
  27.             b = min(b, sb);
  28.         }
  29.         for(int i = find + 1; i < n; i++){
  30.             sc = max(0ll, sc + v[i]);
  31.             sd = min(0ll, sd + v[i]);
  32.             c = max(c, sc);
  33.             d = min(d, sd);
  34.         }
  35.         for(int i = min(b, d); i <= max(a,c); i++){
  36.             s.insert(i);
  37.         }
  38.         a = 0, b = 0, c = 0, d = 0, sa = 0, sb = 0, sc = 0, sd = 0;
  39.         for(int i = find - 1; i >= 0; i--){
  40.             sa += v[i];
  41.             sb += v[i];
  42.             a = max(a, sa);
  43.             b = min(b, sb);
  44.         }
  45.         for(int i = find + 1; i < n; i++){
  46.             sc += v[i];
  47.             sd += v[i];
  48.             c = max(c, sc);
  49.             d = min(d, sd);
  50.         }
  51.         for(int i = v[find] + b + d; i <= v[find] + a + c; i++){
  52.             s.insert(i);
  53.         }
  54.         cout << s.size() << endl;
  55.         for(auto u: s)cout << u << " ";
  56.         cout << endl;
  57.     }
  58. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
5
1 -1 10 1 1
5
-1 -1 -1 -1 -1
2
-1 2
2
7 1
3
1 4 -1
stdout
copy 
8
-1 0 1 2 9 10 11 12 
6
-5 -4 -3 -2 -1 0 
4
-1 0 1 2 
4
0 1 7 8 
6
-1 0 1 3 4 5
https://ideone.com/EXaHti
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!