結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー Pechi
提出日時 2025-12-25 01:21:55
言語 C++17(clang)
(17.0.6 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 5,306 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,249 ms
コンパイル使用メモリ 194,212 KB
実行使用メモリ 26,228 KB
スコア 9,679,644
平均クエリ数 209.83
最終ジャッジ日時 2025-12-25 01:27:53
合計ジャッジ時間 15,935 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 97 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;

#ifdef _MSC_VER
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#endif // _MSC_VER

#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) 	for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) 	for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a)  (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;

chrono::system_clock::time_point starttime;
using namespace std::chrono;
using namespace atcoder;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif

inline float getTime() {
#ifdef DEBUG
    return duration_cast<milliseconds>(system_clock::now() - starttime).count() / 2;
#else
    return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}


int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
inline long long int xor128() {
    static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    long long int t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

struct Solver {
    int ac = 0;
    Solver() {

    }

    vector<array<int, 2>> query(string q) {
        cout << q << endl;
        vector<array<int, 2>> result(30);
        for (int i = 0; i < 30; ++i)cin >> result[i][0] >> result[i][1];
        return result;
    }

    void search(string s, int cnt) {
        vector<int> p(5, 0);
        for (int i = 0; i < 5; ++i)p[i] = i;
        set<pair<ll, string>> judging;
        while (next_permutation(p.begin(), p.end()) != 0) {
            if (cnt == 0)break;
            string q = "";
            for (int i = 0; i < 5; ++i)q += s[p[i]];
            judging.insert({ xor128(),q });
        }
        while (judging.size() != 0) {
            if (cnt == 0)break;
            string q = judging.begin()->second;
            vector<array<int, 2>> result = query(q);
            vector<array<int, 2>> check;
            int add = -ac;
            for (int i = 0; i < 30; ++i) {
                if (result[i][0] == 5)++add;
                else if (result[i][0] + result[i][1] == 5)check.push_back(result[i]);
            }
            ac += add;
            cnt -= add;
            judging.erase(judging.begin());
            auto itr = judging.begin();
            while (itr != judging.end()) {
                bool ok = 0;
                int cnt = 0;
                for (int i = 0; i < 5; ++i)cnt += ((itr->second)[i] == q[i]);
                for (auto c : check) {
                    if (c[0] == cnt)ok = 1;
                }
                if (!ok)itr = judging.erase(itr);
                else ++itr;
            }
        }
    }

    void solve() {
        vector<int> checked(1024, 0);
        set<array<ll, 2>> judging;
        string t = "0123456789";
        for (int x = 0; x < 1024; ++x) {
            bitset<10> b = x;
            if (b.count() != 5)continue;
            judging.insert({ xor128(),x });
        }
        while (judging.size() != 0) {
            bitset<10> b = (*judging.begin())[1];
            bitset<10> nb = b;
            nb.flip();
            int x = b.to_ullong(), nx = nb.to_ullong();
            judging.erase(judging.begin());
            if (checked[x] && checked[nx])continue;
            checked[x] = checked[nx] = 1;
            string q = "", nq = "";
            for (int i = 0; i < 10; ++i) {
                if (b[i])q += t[i];
                else nq += t[i];
            }
            vector<array<int, 2>> result = query(q);
            vector<int> check;
            int p_cnt = 0, n_cnt = 0, ac_cnt = 0;
            for (int i = 0; i < 30; ++i) {
                if (result[i][0] + result[i][1] == 0) ++n_cnt;
                else if (result[i][0] == 5)++ac_cnt;
                else if (result[i][0] + result[i][1] == 5)++p_cnt;
                else check.push_back(result[i][0] + result[i][1]);
            }
            ac = ac_cnt;
            search(q, p_cnt);
            search(nq, n_cnt);
            auto itr = judging.begin();
            while (itr != judging.end()) {
                bool ok = 0;
                for (auto c : check) {
                    if (c == bitset<10>((*itr)[1] & x).count())ok = 1;
                }
                if (!ok)itr = judging.erase(itr);
                else ++itr;
            }
        }
    }

};

int main(int argc, char* argv[]) {
    starttime = chrono::system_clock::now();
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    Solver s;
    s.solve();
    exit(0);
}
0