Submission #168418

#	Time	Username	Problem	Language	Result	Execution time	Memory
168418		Nordway	Xoractive (IZhO19_xoractive)	C++14	94 / 100	17 ms	760 KiB

Xoractive

#include<bits/stdc++.h>
#include"interactive.h"
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=2e5+11;
const int M=1e6+11;
const int inf=1e9;
const ll INF=1e18;
const ll mod=1e9+7;
const double EPS=1e-9;

multiset<int>query(vector<int>v){
  multiset<int>res;
  vector<int>v2=get_pairwise_xor(v);
  for(int i=0;i<sz(v2);i++){
    res.insert(v2[i]);
  }
  return res;
}

multiset<int>num[7];

vector<int>guess(int n){

  vector<int>res;
  res.pb(ask(1));
  multiset<int>S;
  for(int i=0;i<7;i++){
    vector<int>v;
    for(int j=2;j<=n;j++){
      if(((j>>i)&1)==0)continue;
      v.pb(j);
    }
    multiset<int>m1=query(v);
    v.pb(1);
    multiset<int>m2=query(v);
    m2.erase(m2.find(0));
    for(int val:m1)m2.erase(m2.find(val));
    for(int val:m2){
      num[i].insert((val^res[0]));
      S.insert((val^res[0]));
    }
  }
  for(int i=2;i<=n;i++){
    multiset<int>s=S;
    for(int j=0;j<7;j++){
      if(((i>>j)&1)==0)continue;
      multiset<int>m;
      for(int val:num[j]){
        auto it=s.find(val);
        if(it==s.end())continue;
        m.insert(*it);
      }
      s=m;
    }
    for(int j=0;j<7;j++){
      if(((i>>j)&1)==1)continue;
      for(int val:num[j]){
        auto it=s.find(val);
        if(it==s.end())continue;
        s.erase(it);
      }
    }
    res.pb(*s.begin());
  }
  return res;
}

• Subtask 1: 0 / 6
• Subtask 2: 94 / 94