Submission #1205760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205760		mychecksedad	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	30 ms	488 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(vi &A, int l, int r, int other){
    vi v;
    for(int j = l; j <= r; ++j) v.pb(A[j]);
    v.pb(other);
    return Query(v);
  }

  void dfs(int v, int col, vi &vis, vector<vi> &g){
    vis[v] = col;
    for(int u: g[v]){
      if(!vis[u]){
        dfs(u, 3 - col, vis, g);
      }else{
        assert(vis[u] != vis[v]);
      }
    }
  }
} 
void Solve(int n) {
  vi loves(2*n+1);
  done.resize(2*n + 1);
  vector<vi> g(2*n + 1);
  for(int i = 1; i <= 2*n; ++i){
    
    vector<int> vis(2*n+1);
    for(int j = 1; j < i; ++j){
      if(!vis[j]){
        dfs(j, 1, vis, g);
      }
    }

    vi A, B;
    for(int j = 1; j < i; ++j){
      if(vis[j] == 1) A.pb(j);
      else B.pb(j);
    }

    for(int rep = 0; rep < 2; ++rep){
      int last = int(A.size()) - 1;
      for(int rp = 0; rp < 3; ++rp){
        int l = 0, r = last, res = -1;
        if(l > r || query(A, l, r, i) == r - l + 2) break;
        while(l <= r){
          int mid = l+r>>1;
          if(query(A, mid, r, i) < r - mid + 2){
            res = mid;
            l = mid + 1;
          }else{
            r = mid - 1;
          }
        }
        assert(res != -1);
        g[i].pb(A[res]);
        g[A[res]].pb(i);
        last = res - 1;
      }

      swap(A, B);
    }
  }
  for(int i = 1; i <= n*2; ++i){
    if(g[i].size() == 1){
      answer(g[i][0], i);
    }else{
      vi S = {g[i][0], g[i][1], g[i][2]};
      vi A = {S[0], S[1], i};
      vi B = {S[0], S[2], i};
      vi C = {S[1], S[2], i};
      int a = Query(A);
      int b = Query(B);
      int c = Query(C);
      if(a == 1) loves[i] = S[2];
      if(b == 1) loves[i] = S[1];
      if(c == 1) loves[i] = S[0];
    }
  }

  for(int i = 1; i <= n*2; ++i){
    if(g[i].size() == 1){
      answer(g[i][0], i);
    }else{
      for(int u: g[i]){
        if(loves[u] != i && loves[i] != u){
          answer(u, i);
        }
      }
    }
  }
}

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