제출 #235622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235622		doowey	Drvca (COCI19_drvca)	C++14	0 / 110	1083 ms	2812 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;
vector<int> H;
vector<bool>use;

int main(){
  fastIO;
  int n;
  cin >> n;
  H.resize(n);
  use.resize(n);
  for(int i = 0 ; i < n ; i ++ ) cin >> H[i];
  sort(H.begin(),H.end());  
  if(n <= 4){
    cout << 2 << "\n" << H[0] << " " << H[1] << "\n" << 2 << "\n" << H[2] << " " << H[3] << "\n"; 
    return 0;
  }
  int c[3];
  int cur;
  int g;
  for(int it = 0; it < 900 ; it ++ ){
    for(int q = 0; q < 3; q ++ )
      c[q] = (((int)rng() % n) + n) % n;
    sort(c, c + 3);
    if(c[0] == c[1] || c[1] == c[2]) continue;
    for(int i = 0 ; i < n ; i ++ ) use[i] = false;
    g=__gcd(H[c[1]]-H[c[0]],H[c[2]]-H[c[1]]);
    if(H[c[1]] == H[c[0]] || H[c[2]] == H[c[1]])
      g=0;
    cur=H[0];
    vector<int> rem;
    for(int i = 0 ; i < n; i ++ ){
      if(cur == H[i]){
        use[i]=true;
        cur += g;
      }
      else{
        rem.push_back(H[i]);
      }
    }
    bool good = true;
    for(int i = 2; i < rem.size(); i ++ ){
      if(rem[i - 1] - rem[i - 2] != rem[i] - rem[i - 1]){
        good = false;
      }
    }
    if(good){
      vector<int> A, B;
      for(int i = 0 ; i < n; i ++ ){
        if(use[i]) A.push_back(H[i]);
        else B.push_back(H[i]);
      }
      if(B.empty()){
        B.push_back(A[A.size() - 2]);
        B.push_back(A[A.size() - 1]);
        A.pop_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";
      return 0;
    }
    int low = -1;
    for(int i = 0 ; i < n; i ++ ){
      if(!use[i]){
        low = i;
        break;
      }
    }
    for(int i = 0 ; i < n ; i ++ ){
      use[i]=false;
    }
    cur = H[low];
    rem.clear();
    for(int i = low ; i < n ; i ++ ){
      if(cur == H[i]){
        use[i]=true;
        cur += g;
      }
    }
    for(int i = 0 ; i < n; i ++ ){
      if(!use[i])
        rem.push_back(H[i]);
    }
    good=true;
    for(int i = 2; i < rem.size(); i ++ ){
      if(rem[i - 1] - rem[i - 2] != rem[i] - rem[i - 1]){
        good = false;
      }
    }
    if(good){
      vector<int> A, B;
      for(int i = 0 ; i < n; i ++ ){
        if(use[i]) A.push_back(H[i]);
        else B.push_back(H[i]);
      }
      if(B.empty()){
        B.push_back(A[A.size() - 2]);
        B.push_back(A[A.size() - 1]);
        A.pop_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";
      return 0;
    }
  }
  cout << -1 << "\n";
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

drvca.cpp: In function 'int main()':
drvca.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i < rem.size(); i ++ ){
                    ~~^~~~~~~~~~~~
drvca.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i < rem.size(); i ++ ){
                    ~~^~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30