Submission #235660

#	Time	Username	Problem	Language	Result	Execution time	Memory
235660		doowey	Drvca (COCI19_drvca)	C++14	50 / 110	1086 ms	2940 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);
}

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 (stderr)

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