結果
問題 | No.862 XORでX |
ユーザー |
![]() |
提出日時 | 2019-08-09 22:49:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,608 bytes |
コンパイル時間 | 738 ms |
コンパイル使用メモリ | 77,108 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-19 14:56:39 |
合計ジャッジ時間 | 2,750 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;using ll = long long;int main() {ios::sync_with_stdio(false);cin.tie(0);constexpr int A = 100005;int n, x;cin >> n >> x;int b = n > A - n;if (b) {n = A - n;for (int i = 1; i <= A; i++) {x ^= i;}}vector<int> r(A + 1);int c = x < 4 ? 4 : 1;switch (n % 4) {case 0:if (x != 0) {r[x] = 1;r[1 * c] = 1;r[2 * c] = 1;r[3 * c] = 1;n -= 4;}break;case 1:if (x != 0) {r[x] = 1;} else {int s = 0;for (int j = 0; j < 4; j++) {int t = 3 << j;r[t] = 1;s ^= t;}r[s] = 1;n -= 4;}break;case 2:if (x != 0) {r[x ^ c] = 1;r[c] = 1;} else {int s = 0;for (int j = 0; j < 5; j++) {int t = 3 << j;r[t] = 1;s ^= t;}r[s] = 1;n -= 4;}break;case 3:r[x ^ 1 * c] = 1;r[x ^ 2 * c] = 1;r[x ^ 3 * c] = 1;break;}n -= n % 4;for (int i = 4; n > 0; i += 4) {int f = 0;for (int j = 0; j < 4; j++) {if (r[i + j]) f = 1;}if (f == 0) {for (int j = 0; j < 4; j++) {r[i + j] = 1;}n -= 4;}}n = x = 0;for (int i = 1; i <= A; i++) {if (r[i] ^ b) {cout << i << '\n';n++;x ^= i;}}cout << flush;//cout << n << ' ' << x << endl;//Nが立っているビット数以下なら簡単//より大きいとき、1つのビットだけが立ってるやつを除いて適当に取る 適当に取る過程でpopcntをコントロールできない//1<<16のビットを持つ数が少ない?個数だけで言えば多いよな//4の倍数から連続する4つのxorは0になる これで数を稼ぐ//n%4で場合分け 1のときは簡単 0のときは1,10,11で0を作る、ただし... 2のときはx^1と1、ただしx==1のときはx^10と10 3のときはx^1,x^10,x^11、ただしx<4のときはx^100,x^1000,x^1100//反転して0になった場合return 0;}