結果
| 問題 |
No.3120 Lower Nim
|
| ユーザー |
 eiya5498513
|
| 提出日時 | 2025-04-20 10:19:40 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 217 ms / 2,000 ms |
| コード長 | 7,103 bytes |
| コンパイル時間 | 3,643 ms |
| コンパイル使用メモリ | 213,260 KB |
| 実行使用メモリ | 26,344 KB |
| 平均クエリ数 | 2685.91 |
| 最終ジャッジ日時 | 2025-04-20 10:19:52 |
| 合計ジャッジ時間 | 11,497 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 43 |
ソースコード
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 26450 )
#pragma warning( disable : 26451 )
#pragma warning( disable : 26498 )
#pragma warning( disable : 4459 )
#endif
#include <atcoder/all>
#ifdef _MSC_VER
#pragma warning( pop )
#endif
auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;
#if 0
// 定数 H
constexpr uint32_t H0[] = {
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};
// 定数 K
constexpr uint32_t K[] = {
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
#if 0
void func()
{
// メッセージを N 個のメッセージブロック M^(0), ..., M^(N) に分割
auto N = 1; // N = 1
uint32_t W = [];
uint32_t H[8] = {};
for (let i = 0; i < 8; i++) {
H[i] = H0[i];
}
// 各メッセージブロックに対して処理
for (int t = 0; t < 64; t++) {
if (t < 16) {
// W[t] のスタートライン
let p = (i - 1) * 64 + t * 4;
// 8 ビットずつ左につめて、32 ビットの M_t^(i) を作成.
W[t] = (msg[p] << 24) + (msg[p + 1] << 16) + (msg[p + 2] << 8) + msg[p + 3];
// W[0] = 0x48656c6c (最初の4バイト: "Hell")
// W[1] = 0x6f800000 (次の4バイト: "o" + padding)
// W[2] から W[14] = 0x00000000 (padding)
// W[15] = 0x00000028 (メッセージ長: 40)
}
else {
W[t] = (sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16]) & 0xffffffff;
}
}
uint32_t a = H[0];
uint32_t b = H[1];
uint32_t c = H[2];
uint32_t d = H[3];
uint32_t e = H[4];
uint32_t f = H[5];
uint32_t g = H[6];
uint32_t h = H[7];
for (let t = 0; t < 64; t++) {
let T1 = (h + SIGMA1(e) + Ch(e, f, g) + K[t] + W[t]) & 0xffffffff;
let T2 = (SIGMA0(a) + Maj(a, b, c)) & 0xffffffff;
next_h = g;
next_g = f;
next_f = e;
next_e = (d + T1) & 0xffffffff;
next_d = c;
next_c = b;
next_b = a;
next_a = (T1 + T2) & 0xffffffff;
h = next_h;
g = next_g;
f = next_f;
e = next_e;
d = next_d;
c = next_c;
b = next_b;
a = next_a;
}
// ハッシュ値を符号なし32ビット整数に変換
H[0] = a + H[0];
H[1] = b + H[1];
H[2] = c + H[2];
H[3] = d + H[3];
H[4] = e + H[4];
H[5] = f + H[5];
H[6] = g + H[6];
H[7] = h + H[7];
}
#endif
// 1. ビット操作に使う関数
// 1-1. 右に n ビット巡回
uint32_t ROTR(uint32_t x, uint32_t n) {
return (x >> n) | (x << (32 - n));
}
// 1-2. 右に nビットシフト
uint32_t SHR(uint32_t x, uint32_t n) {
return x >> n;
}
// 2. SHA256 で使用する 6つの関数
// 2-1. Choose
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z) {
return (x & y) ^ (~x & z);
}
// 2-2. Majority
uint32_t Maj(uint32_t x, uint32_t y, uint32_t z) {
return (x & y) ^ (x & z) ^ (y & z);
}
// 2-3
uint32_t sigma0(uint32_t x) {
return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3);
}
// 2-4
uint32_t sigma1(uint32_t x) {
return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10);
}
// 2-5
uint32_t SIGMA0(uint32_t x) {
return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);
}
// 2-6
uint32_t SIGMA1(uint32_t x) {
return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25);
}
void decode()
{
uint32_t a = 0 - H[0];
uint32_t b = 0 - H[1];
uint32_t c = 0 - H[2];
uint32_t d = 0 - H[3];
uint32_t e = 0 - H[4];
uint32_t f = 0 - H[5];
uint32_t g = 0 - H[6];
uint32_t h = 0 - H[7];
uint32_t W[64] = {};
for (int t = 63; t >= 0; --t)
{
// (T1 + T2) = a;
// (prev_d + T1) = e;
const auto prev_a = b;
const auto prev_b = c;
const auto prev_c = d;
const auto prev_e = f;
const auto prev_f = g;
const auto prev_g = h;
const auto T2 = SIGMA0(prev_a) + Maj(prev_a, prev_b, prev_c);
const auto T1 = a - T2; // (T1 + T2) = a;
const auto prev_d = e - T1; // (prev_d + T1) = e;
W[t] + prev_h = T1 - (SIGMA1(prev_e) + Ch(prev_e, prev_f, prev_g) + K[t]);
h = prev_h;
g = prev_g;
f = prev_f;
e = prev_e;
d = prev_d;
c = prev_c;
b = prev_b;
a = prev_a;
}
assert(a == H[0]);
assert(b == H[1]);
assert(c == H[2]);
assert(d == H[3]);
assert(e == H[4]);
assert(f == H[5]);
assert(g == H[6]);
assert(h == H[7]);
std::string msg;
for (int t = 0; t < 16; t++) {
msg += char((W[t] >> 24) & 0xff);
msg += char((W[t] >> 16) & 0xff);
msg += char((W[t] >> 8) & 0xff);
msg += char((W[t] >> 0) & 0xff);
}
std::cout << msg;
}
#endif
int32_t K= 2000000;
int32_t N;
int32_t A[20000];
int32_t count_bit[20];
void take_num(int32_t num) {
using std::endl;
K = num;
for (size_t i = 0; i < N; i++)
{
if (A[i] >= num) {
for (size_t b = 0; b < 20; b++) {
if ((A[i] & (1 << b)) != 0) {
count_bit[b] -= 1;
}
}
A[i] -= num;
for (size_t b = 0; b < 20; b++) {
if ((A[i] & (1 << b)) != 0) {
count_bit[b] += 1;
}
}
out << (i + 1) << ' ' << num << endl;
int res;
in >> res;
if (res != 0) {
std::exit(0);
}
return;
}
}
throw 1;
}
void judge() {
int i, x;
in >> i >> x;
i -= 1;
int ret;
in >> ret;
if (ret != 0) {
std::exit(0);
}
K = x;
for (size_t b = 0; b < 20; b++) {
if ((A[i] & (1 << b)) != 0) {
count_bit[b] -= 1;
}
}
A[i] -= x;
for (size_t b = 0; b < 20; b++) {
if ((A[i] & (1 << b)) != 0) {
count_bit[b] += 1;
}
}
}
int main()
{
using std::endl;
in.sync_with_stdio(false);
out.sync_with_stdio(false);
in.tie(nullptr);
out.tie(nullptr);
in >> N;
for (size_t i = 0; i < N; i++)
{
in >> A[i];
}
for (size_t i = 0; i < N; i++)
{
for (size_t b = 0; b < 20; b++) {
if ((A[i] & (1 << b)) != 0) {
count_bit[b] += 1;
}
}
}
int now_b = -1;
for (size_t b = 0; b < 20; b++) {
if (count_bit[b] % 2 != 0) {
now_b = b;
out << "First" << endl;
take_num(1 << b);
break;
}
}
if (now_b == -1) {
out << "Second" << endl;
}
for (;;) {
judge();
for (size_t b = 0; b < 20; b++) {
if (count_bit[b] % 2 != 0) {
now_b = b;
take_num(1 << b);
break;
}
}
}
}
#endif