Submission #1204910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204910		mychecksedad	Chameleon's Love (JOI20_chameleon)	C++20	0 / 100	17 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 {
  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);
    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};
      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){
    if(done[i]) continue;
    int l = n + 1, r = 2*n, res = -1;
    while(l <= r){
      int mid = l+r>>1;
      if(query2(l, mid, i, go[i]) == mid - l + 1){
        res = mid;
        r = mid - 1;
      }else{
        l = mid + 1;
      }
    }
    if(res != -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