oj.uz

Submission #235622

# Submission time Handle Problem Language Result Execution time Memory
235622 2020-05-28T21:02:21 Z doowey Drvca (COCI19_drvca) C++14
0 / 110
 1000 ms 2812 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;
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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 5 ms 380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 5 ms 380 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2812 KB Output is correct
2 Correct 98 ms 2604 KB Output is correct
3 Correct 43 ms 2760 KB Output is correct
4 Correct 118 ms 2588 KB Output is correct
5 Correct 44 ms 2720 KB Output is correct
6 Correct 57 ms 2596 KB Output is correct
7 Correct 44 ms 2784 KB Output is correct
8 Correct 77 ms 2672 KB Output is correct
9 Execution timed out 1083 ms 1880 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 5 ms 380 KB Output isn't correct
10 Halted 0 ms 0 KB -