結果

問題 No.3120 Lower Nim
ユーザー hardenisthegoat
提出日時 2025-04-19 03:01:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 261 ms / 2,000 ms
コード長 6,552 bytes
コンパイル時間 2,858 ms
コンパイル使用メモリ 232,316 KB
実行使用メモリ 26,212 KB
平均クエリ数 2686.66
最終ジャッジ日時 2025-04-19 03:01:51
合計ジャッジ時間 11,937 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ar array
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define pob pop_back()
#define nn "\n"
#define onn << "\n"
#define ee endl
#define oee << endl
#define ss " "
#define oss << " "
#define sei unordered_set<int, custom_hash>
#define ses unordered_set<string>
#define ma unordered_map
#define maii unordered_map<int, int, custom_hash>
#define vc vector
#define id1 int n; cin >> n;
#define gls getline(cin, s)
#define sinf 1e9
#define inf (int) 1e18
#define co cout <<
#define sp(i) setprecision(i) <<
#define f1(i, a) for (auto& i : a)
#define f2(i, j, a) for (auto& [i, j] : a)
#define f3(i, j, k, a) for (auto& [i, j, k] : a)
#define be(s) s.begin(), s.end()
#define rbe(s) s.rbegin(), s.rend()
#define bb(s) s.begin(), s.begin()
#define ctz(x) __builtin_ctzll(x)
#define cb(x) __builtin_popcountll(x)
#define ff(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define i128 __int128_t
#define lb lower_bound
#define ub upper_bound
#define ook order_of_key
#define fbo find_by_order
#define fn function
#define bs bitset
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

typedef unsigned long long ull;
typedef pair<int, string> pis;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<pair<int,int>> vp;
typedef vector<vector<int>> vvi;

#pragma GCC optimize("Ofast,unroll-loops")

#ifdef LOCAL
#include "debug_util.h"
#else
#define help(...)
#define helpArray(...)
#define io
#define _time
#define _siu
#endif

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os;}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second; return is;}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");} return os;}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is;}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<class T>
bool constexpr chmin(T &a, T b) {
    if (a > b) {a = b;return true;}
    return false;
}

template<class T>
bool constexpr chmax(T &a, T b) {
    if (a < b) {a = b;return true;}
    return false;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ans(sz(A));
  iota(be(ans), 0);
  sort(be(ans),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ans;
}


//64b
long long lsb(long long x) {    return x & -x;}
long long msb(long long x) {    return (1ll << (63-__builtin_clzll(x))) & x;}
void onb(long long& x, int i) { x |= (1ll << i);}
void offb(long long& x, int i) { x &= ~(1ll << i);}
bool hb(long long x, int i) { return ((1ll << i) & x) != 0;}
long long bit(long long x) { return 1ll << x;}

void YES(bool t = 1) { cout << (t ? "YES" : "NO") << "\n"; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << (t ? "Yes" : "No") << "\n"; }
void No(bool t = 1) { Yes(!t); }



template<typename T>
vector<pair<T, int>> pfy(vector<T>& f) {
    vector<pair<T, int>> v;
    for (int i = 0; i < f.size(); i++) {
        v.push_back({f[i], i});
    }
    return v;
}

bool inrange(int i, int j, int limi, int limj) {
    return i >= 0 && i < limi && j >= 0 && j < limj;
}

typedef tuple<int,int,int> iii;
vector<char> cao = {'C','D','H','S'};
int dr8[] = {0,-1,0, 1, 1, 1, -1, -1};
int dc8[] = {-1, 0, 1, 0, 1, -1, 1, -1};
//n,w,e,s
int dr[] = {-1, 0, 0, 1};
int dc[] = {0,-1,1, 0};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

// Define a tree-based set with integer keys
template <typename T>
using Tee = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void sui() {
  id1;
  vi v(n);
  cin>>v;
  vi backup  = v;
  set<pii> st;
  ff(i,0,n) st.insert({v[i], i});
  auto aggress = [&](int bit) {
    int cur = bit;
    while (!st.empty()) {
      auto it = st.lb({cur, 0});
      auto [a,b] = *it;
      v[b] -= cur;
      st.erase(it);
      cout << b+1 << " " << cur << endl;
      if (a != cur) {
        st.insert({a-cur, b});
      }
      int ret;
      cin>>ret;
      if (abs(ret) == 1) return;
      int i,x;
      cin>>i>>x;
      --i;
      st.erase(st.lb({v[i],i}));
      v[i] -= x;
      cur = lsb(x);
      if (v[i]) st.insert({v[i], i});
      cin>>ret;
      if (abs(ret) == 1) return;
    }
  };
  ff(i,0,20) {
    int cnt = 0;
    ff(j,0,n) {
      if (hb(v[j], i)) {
        cnt++;
      }
    }
    if (cnt%2) {
      co "First" oee;
      aggress(bit(i));
    }
  }
  co "Second" oee;
  auto react = [&]() {
    int cur;
    int ret;

    while (!st.empty()) {
      int i,x;
      cin>>i>>x;
      cur = lsb(x);
      --i;
      st.erase(st.lb({v[i],i}));
      v[i] -= x;
      if (v[i]) st.insert({v[i], i});
      cin>>ret;
      // if (cb(x)%2) {
      //   aggress(lsb(x));
      //   return;
      // }
      if (abs(ret) == 1) return;
      auto it = st.lb({cur, 0});
      auto [a,b] = *it;
      v[b] -= cur;
      st.erase(it);
      cout << b+1 << " " << cur << endl;
      if (a != cur) {
        st.insert({a-cur, b});
      }
      cin>>ret;
      if (abs(ret) == 1) return;
    }
  };
  react();
}

signed main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  auto start = std::chrono::high_resolution_clock::now();
  io;
  int n = 1;
  // cin >> n;
  ff(i,0,n)
    sui();
  _time;
  return 0;
}
0