Submission #235679

#	Time	Username	Problem	Language	Result	Execution time	Memory
235679		doowey	Drvca (COCI19_drvca)	C++14	110 / 110	116 ms	8432 KiB

drvca

#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){
    if(size() < 2){
      insert(x);
      return;
    }
    auto it = insert(x);
    it -- ;
    bad += !good(it);
  }
  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);
      }
    }
    it = erase(it);
    if(it != end()){
      bad += !good(it);
    }
    if(it != begin()){
      it -- ;
      bad += !good(it);
    }
  }
};

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: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30