oj.uz

Submission #443144

# Submission time Handle Problem Language Result Execution time Memory
443144 2021-07-09T19:30:41 Z Dipto_Debdip Drvca (COCI19_drvca) C++14
0 / 110
 1000 ms 141864 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
bool chk(vector<ll> v) {
  set<ll> st;
  for (ll i = 0; i < (ll) (v.size()) - 1; i++) {
    st.insert(v[i] - v[i + 1]);
  }
  return (st.size() == 1 || st.size() == 0);
}
int main(int argc, char const *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, k;
  vector<ll> v;
  map<ll, ll> mp;
  cin >> n;
  for (ll i = 0; i < n; i++) {
    cin >> k;
    mp[k]++;
    v.push_back(k);
  }
  set<ll> st;
  sort(v.begin(), v.end());
  for (ll i = 0; i < n; i++) {
    for (ll j = i + 1; j < n; j++) {
      st.insert(v[j] - v[i]);
    }
  }
  ll f = 0;
  for (ll c : st) {
    if (c == 0) continue;
    //cout << "c = " << c << endl;
    for (ll i = 0; i < n; i++) {
      vector<ll> f = {v[i]};
      map<ll, ll> mp2;
      mp2[v[i]]++;
      ll ff = 2;
      while (ff) {
        map<ll, ll> cop;
        for (ll jj : f) cop[jj]++;
        vector<ll> s;
        for (ll j : v) {
          if (cop[j]) cop[j]--;
          else s.push_back(j);
        }
        //cout << "hi" << endl;
        //s.erase(s.begin());
        if (chk(s) && chk(f) && (ll) (s.size() + (ll) f.size()) == n) {
          cout << f.size() << endl;
          for (ll ii : f) cout << ii << " ";
          cout << endl;
          cout << endl;
          cout << s.size() << endl;
          for (ll jj : s) cout << jj << " ";
          cout << endl;
          return 0;
        }
        if (mp[f.back() + c] == 0) ff--;
        else f.push_back(f.back() + c);
      }
    }
  }
  if (*st.begin() == 0 && st.size() == 1) {
    cout << 1 << " " << endl << v[0] << endl;
    cout << n - 1 << endl;
    for (ll i = 1; i < n; i++) cout << v[i] << " ";
    cout << endl;
    return 0;
  }
  cout << -1 << endl;
  return 0;
}

Compilation message

drvca.cpp: In function 'int main(int, const char**)':
drvca.cpp:30:6: warning: unused variable 'f' [-Wunused-variable]
   30 |   ll f = 0;
      |      ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 3 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 3 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 141864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 3 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 0 ms 204 KB Output isn't correct
13 Halted 0 ms 0 KB -