oj.uz

Submission #235669

# Submission time Handle Problem Language Result Execution time Memory
235669 2020-05-29T09:45:55 Z doowey Drvca (COCI19_drvca) C++14
0 / 110
 164 ms 7308 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);
}

int bad;

struct F : multiset<int>{
  bool good(iterator it){
    auto nx = it;
    nx ++ ;
    if(nx == end() || it == begin()) return true;
    auto pv = it;
    pv -- ;
    return ((*it) - (*pv))==((*nx) - (*it));
  }
  void add(int x){
    auto it = lower_bound(x);
    
    auto pv = it;
    if(it != begin()){
      pv -- ;
      bad -= !good(pv);
    }
    pv = it;
    if(pv != end()){
      pv ++ ;
      if(pv != end()){
        bad -= !good(pv);
      }
    }
    it = insert(x);
    bad += !good(it);
    pv = it;
    if(it != begin()){
      pv -- ;
      bad += !good(pv);
    }
    pv = it;
    if(pv != end()){
      pv ++ ;
      if(pv != end()){
        bad -= !good(pv);
      }
    }
  }
  void rem(int x){
    auto it = lower_bound(x);
    bad -= !good(it);
    auto pv = it; 
    if(pv != begin()){
      pv -- ;
      bad -= !good(pv);
    }
    auto nx = it;
    if(nx != end()){
      nx ++ ;
      if(nx != end()){
        bad -= !good(nx);
      }
    }
    nx = erase(it);
    if(nx != end()){
      bad += !good(nx);
    }
    if(nx != begin()){
      nx -- ;
      bad += !good(nx);
    }
  }
};

F cur;

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 el, dif;
  for(int ii = 0 ; ii < 3; ii ++ ){
    for(int jj = ii + 1; jj < 3; jj ++ ){
      dif = hh[jj] - hh[ii];
      el = hh[jj] + dif;
      bad = 0;
      cur.clear();
      for(int x = 0 ;x < n; x ++ ){
        if(x == ii || x == jj) continue;
        cur.add(hh[x]);
      }
      vector<int> cc = {hh[ii], hh[jj]};
      vector<int> dd;
      if(bad == 0){
        for(auto p : cur) dd.push_back(p);
        print_solution(cc,dd);
      }
      for(int x = jj + 1; x < n ; x ++ ){
        if(hh[x] == el){
          cc.push_back(hh[x]);
          cur.rem(hh[x]);
          if(bad == 0){
            for(auto p : cur){
              dd.push_back(p);
            }
            print_solution(cc,dd);
          }
          el += dif;
        }
      }
      
    }
  }
  cout << -1 << "\n";
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 7308 KB Output isn't correct
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 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -