oj.uz

Submission #235660

# Submission time Handle Problem Language Result Execution time Memory
235660 2020-05-29T09:04:06 Z doowey Drvca (COCI19_drvca) C++14
50 / 110
 1000 ms 2940 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (int)1e5 + 10;
int hh[N];
bool ok[N];
int n;

void print_solution(vector<int> A, vector<int> B){
  if(B.empty()){
    B.push_back(A.back());
    A.pop_back();
  }
  cout << A.size() << "\n";
  for(auto x : A ) cout << x << " ";
  cout << "\n";
  cout << B.size() << "\n";
  for(auto x : B ) cout << x << " ";
  cout << "\n";
  exit(0);
}

void check(){
  vector<int> ai, bi;
  for(int i = 0 ; i < n; i ++ ){
    if(ok[i]){
      ai.push_back(hh[i]);
    }
    else{
      bi.push_back(hh[i]);
    }
  }
  for(int i = 2; i < bi.size(); i ++ ){
    if(bi[i] - bi[i - 1] != bi[i - 1] - bi[i - 2]) return;
  }
  print_solution(ai, bi);
}

int main(){
  fastIO;
  cin >> n;
  for(int i = 0 ; i < n; i ++ ) 
    cin >> hh[i];
  sort(hh, hh + n);
  if(n == 2){
    cout << 1 << "\n" << hh[0] << "\n" << 1 << "\n" << hh[1] << "\n";
    return 0;
  }
  if(n == 3){
    cout << 2 << "\n" << hh[0] << " " << hh[1] << "\n" << 1 << "\n" << hh[2] << "\n";
    return 0;
  }
  if(n == 4){
    cout << 2 << "\n" << hh[0] << " " << hh[1] << "\n" << 2 << "\n" << hh[2] << " " << hh[3] << "\n";
    return 0;
  }
  int cur, dif;
  for(int ii = 0 ; ii < 3; ii ++ ){
    for(int jj = ii + 1; jj < 3; jj ++ ){
      for(int q = 0 ;q < n; q ++ )
        ok[q] = false;
      dif = hh[jj] - hh[ii];
      cur = hh[jj] + dif;
      ok[ii]=true;
      ok[jj]=true;
      check();
      for(int x = jj + 1; x < n ; x ++ ){
        if(hh[x] == cur){
          cur += dif;
          ok[x]=true;
          check();
        }
      }
      
    }
  }
  cout << -1 << "\n";
  return 0;
}

Compilation message

drvca.cpp: In function 'void check()':
drvca.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 2; i < bi.size(); i ++ ){
                  ~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 2940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Execution timed out 1086 ms 2940 KB Time limit exceeded
32 Halted 0 ms 0 KB -