Submission #296496

#	Time	Username	Problem	Language	Result	Execution time	Memory
296496		BThero	Park (JOI17_park)	C++17	10 / 100	186 ms	1048 KiB

park

// chrono::system_clock::now().time_since_epoch().count()
#include "park.h"
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
static int tmp_arr[2005];
static int n;

bool ask(int a, int b, vector<int> &vec) {
  if (a > b) {
    swap(a, b);
  }

  fill(tmp_arr, tmp_arr + n, 0);
  
  for (int x : vec) {
    tmp_arr[x] = 1;
  }
  
  return Ask(a, b, tmp_arr);
}

void report(int a, int b) {
  if (a > b) {
    swap(a, b);
  }

  Answer(a, b);
}

namespace subtask1 {  
  void solve() {
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        vector<int> S;
        S.pb(i);
        S.pb(j);
        
        if (ask(i, j, S)) {
          report(i, j);
        }
      }
    }
  }
};

namespace subtask2 {
  vector<int> calc(int L, int R, vector<int> S) {
    vector<int> ret;
    
    if (S.size() == 2) {
      ret.pb(L);
      ret.pb(R);
      return ret;
    }
    
    int m = rnd() % S.size();
    
    while (S[m] == L || S[m] == R) {
      m = rnd() % S.size();
    }
    
    int M = S[m];
    vector<int> A, B;
    A.pb(L);
    A.pb(M);
    B.pb(M);
    B.pb(R);
    
    for (int x : S) {
      if (x != L && x != M && x != R) {
        vector<int> S2 = S;
        S2.erase(find(all(S2), x));
      
        if (ask(L, M, S2)) {
          B.pb(x);
        }
        else {
          A.pb(x);
        }
      }
    }
    
    A = calc(L, M, A);
    B = calc(M, R, B);
    
    for (int x : A) {
      ret.pb(x);
    }
    
    ret.pop_back();
    
    for (int x : B) {
      ret.pb(x);
    }
    
    return ret;
  }
  
  void solve() {    
    vector<int> S;
    
    for (int i = 0; i < n; ++i) {
      S.pb(i);
    }
    
    S = calc(0, n - 1, S);
    
    for (int i = 0; i + 1 < n; ++i) {
      report(S[i], S[i + 1]);
    }
  }
};

namespace subtask3 {
  vector<vector<int>> f(vector<int> S, int v) {
    S.erase(find(all(S), v));
    vector<vector<int>> comp;
    
    for (int x : S) {
      vector<int> tmp;
      tmp.pb(v);
      tmp.pb(x);
      
      if (ask(v, x, tmp)) {
        report(v, x);
        comp.pb(vector<int>(1, x));
      }
    }
    
    vector<int> T = S;
    
    for (vector<int> vec : comp) {
      S.erase(find(all(S), vec[0]));
    }
    
    for (int x : S) { 
      int p = 0;
      vector<int> perm(comp.size());
      iota(all(perm), 0);
      //random_shuffle(all(perm));
      
      while (p + 1 < (int)comp.size() && !ask(comp[perm[p]][0], x, T)) {
        ++p;
      }
      
      comp[perm[p]].pb(x);
    }
    
    return comp;
  }

  void go(vector<int> sub) {
    if ((int)sub.size() == 1) {
      return;
    }
    
    if ((int)sub.size() == 2) {
      report(sub[0], sub[1]);
      return;
    }
    
    int v = sub[rnd() % (int)sub.size()];  
    vector<vector<int>> comp = f(sub, v);
    vector<int> others = sub;
    others.erase(find(all(others), v));
    
    for (vector<int> vec : comp) {
      others.erase(find(all(others), vec[0]));
    }
    
    if (others.size() > 5) {
      int u = others[rnd() % (int)others.size()];
      vector<vector<int>> comp2 = f(sub, u), comp3;
      int ptr_v = 0, ptr_u = 0;
      
      while (find(all(comp[ptr_v]), u) == comp[ptr_v].end()) {
        ++ptr_v;
      }
      
      while (find(all(comp2[ptr_u]), v) == comp2[ptr_u].end()) {
        ++ptr_u;
      }
      
      vector<int> used(n + 5, 0);
      
      for (int i = 0; i < (int)comp.size(); ++i) {
        if (i != ptr_v) {
          comp3.pb(comp[i]);
          
          for (int x : comp[i]) {
            used[x] = 1;
          }
        }
      }
      
      for (int i = 0; i < (int)comp2.size(); ++i) {
        if (i != ptr_u) {
          comp3.pb(comp2[i]);
          
          for (int x : comp[i]) {
            used[x] = 1;
          }
        }
      }
      
      vector<int> ext;
      
      for (int x : sub) {
        if (x != u && x != v && !used[x]) {
          ext.pb(x);
        }
      }
      
      comp3.pb(ext);
      comp = comp3;
    }
    
    for (vector<int> nsub : comp) {
      go(nsub);
    }
  }
  
  void solve() {
    vector<int> S;
    
    for (int i = 0; i < n; ++i) {
      S.pb(i);
    }
    
    go(S);
  }
};

void Detect(int T, int N) {
  n = N;

  if (T == 1) {
    subtask1::solve();
  }
  else {
    subtask3::solve();
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23