Submission #1204923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204923		mychecksedad	Chameleon's Love (JOI20_chameleon)	C++20	0 / 100	19 ms	436 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 5e3+10, K = 52, MX = 30;

namespace {

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int rn(int l, int r){
    return uniform_int_distribution<int>(l,r)(rng);
  }

  vector<bool> done;
  void answer(int x, int y){
    if(done[x] || done[y]) return;
    done[x] = done[y] = 1;
    cerr << x << ' ' << y << '\n';
    Answer(x, y);
  }

  int query(int l, int r, int other){
    vi v;
    for(int j = l; j <= r; ++j) v.pb(j);
    v.pb(other);
    return Query(v);
  }
  int query2(int l, int r, int other, int other2){
    vi v;
    for(int j = l; j <= r; ++j) v.pb(j);
    v.pb(other);
    if(other2 < l || r < other2)
      v.pb(other2);
    return Query(v);
  }

} 
void Solve(int n) {
  vi go(2*n+1);
  done.resize(2*n + 1);
  for(int i = n + 1; i <= 2*n; ++i){
    int last = n;
    vi S;
    for(int rep = 0; rep < 3; ++rep){
      int l = 1, r = last, res = -1;
      while(l <= r){
        int mid = l+r>>1;
        if(query(mid, r, i) < r - mid + 2){ // it contains smth
          res = mid;
          l = mid + 1;
        }else{
          r = mid - 1;
        }
      }
      if(res == -1) break;
      S.pb(res);
      last = res - 1;
    }
    // for(int x: S) cerr << x << ' ';
    // cerr << i << '\n';
    if(S.size() == 1){
      answer(i, S[0]);
    }else{
      vi A = {S[0], S[1], i};
      vi B = {S[1], S[2], i};
      vi C = {S[0], S[2], i};

      vector<vi> order;
      order.pb(A);
      order.pb(B);
      order.pb(C);
      for(int i = 0; i < 3; ++i) order[i].swap(order[rn(0, i)]);
        // randomize this order to save up half the queries (around 1.5N)
      for(int j = 0; j < 3; ++j){
        if(Query(order[j]) == 1){
          if(order[j] == A) go[S[2]] = i;
          if(order[j] == B) go[S[0]] = i;
          if(order[j] == C) go[S[1]] = i;
          break;
        }
      }

      // int a = Query(A);
      // int b = Query(B);
      // int c = Query(C);
      // if(a == 1) go[S[2]] = i;
      // else if(b == 1) go[S[0]] = i;
      // else go[S[1]] = i; // a male is loved by which female
    }
  }  

  // for(int i= 1; i <= n; ++i) cerr << go[i] << '\n';

  for(int i = 1; i <= n; ++i){
    if(done[i]) continue;

    int x = rn(0, 1);

    // randomize whether searching from right or left
    if(x == 0){
      int l = n + 1, r = 2*n, res = -1;
      while(l <= r){
        int mid = l+r>>1;
        // cerr << l << ' ' << mid << ' ' << i << ' ' << go[i] << '\n';
        // cerr << query2(l, mid, i, go[i]) << '\n';
        int sz = mid - l + 1 + (l <= go[i] && go[i] <= mid ? -1 : 0);
        if(query2(l, mid, i, go[i]) == sz){
          res = mid;
          r = mid - 1;
        }else{
          l = mid + 1;
        }
      }
      // cerr << i << ' ' << res << '\n';

      // the point we found might be either the one that is equal with this male, or it's the one male loves
      assert(res != -1);
      vi p = {i, go[i], res};
      int a = Query(p);
      if(a == 1){
        answer(i, res); // we found it, yea
      }else{
        // we gotta search n + 1 .... res - 1
        l = n + 1, r = res - 1;
        while(l <= r){
          int mid = l+r>>1;
          int sz = mid - l + 1 - (l <= go[i] && go[i] <= mid ? -1 : 0);
          if(query2(l, mid, i, go[i]) == sz){
            res = mid;
            r = mid - 1;
          }else{
            l = mid + 1;
          }
        }
        answer(i, res);
      }
    }else{
      int l = n + 1, r = 2*n, res = -1;
      while(l <= r){
        int mid = l+r>>1;
        int sz = r - mid + 1 + (mid <= go[i] && go[i] <= r ? -1 : 0);
        if(query2(mid, r, i, go[i]) == sz){
          res = mid;
          l = mid + 1;
        }else{
          r = mid - 1;
        }
      }

      // the point we found might be either the one that is equal with this male, or it's the one male loves
      assert(res != -1);
      vi p = {i, go[i], res};
      int a = Query(p);
      if(a == 1){
        answer(i, res); // we found it, yea
      }else{
        // we gotta search res + 1 .... 2 * n
        l = res + 1, r = 2 * n;
        while(l <= r){
          int mid = l+r>>1;
          int sz = r - mid + 1 + (mid <= go[i] && go[i] <= r ? -1 : 0);
          if(query2(mid, r, i, go[i]) == sz){
            res = mid;
            l = mid + 1;
          }else{
            r = mid - 1;
          }
        }
        answer(i, res);
      }

    }
  }


  // vector<vi> S(2*n+1);
  // done.resize(2*n+1);
  // vector<int> v, go(n*2+1);
  // for(int i = 1; i <= 2*n; ++i) v.pb(i);
  // for(int i = 1; i <= n*2; ++i){
  //   for(int j = 1; j <= n*2; ++j){
  //     if(i != j){
  //       vi p; p.pb(i);
  //       p.pb(j);
  //       int x = Query(p);
  //       if(x == 1){
  //         S[i].pb(j);
  //       }
  //     }
  //   }
  
  // }
  // for(int i = 1; i <= 2*n; ++i){
  //   for(int x: S[i]){
  //     if(go[i] != x && go[x] != i){
  //       answer(i, x);
  //     }
  //   }
  // }
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36