結果

問題 No.624 Santa Claus and The Last Dungeon
ユーザー e869120
提出日時 2017-12-23 23:35:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,790 bytes
コンパイル時間 1,355 ms
コンパイル使用メモリ 87,756 KB
実行使用メモリ 25,208 KB
平均クエリ数 439.81
最終ジャッジ日時 2024-07-16 15:04:42
合計ジャッジ時間 5,757 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::tuple<int, int, int> Get(std::vector<std::__cxx11::basic_string<char> >)':
main.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <tuple>
#include <vector>
#include <tuple>
#include <string>
#include <ctime>
using namespace std;
int Q, a[200], b[100]; bool used[100]; vector<int>B;
int Debug = 1, Queries;
tuple<int, int, int> Get(vector<string>V) {
    Queries++;
    if (Debug == 0) {
        int c[3] = { 0,0,0 };
        for (int i = 0; i < 100; i++) {
            string U = to_string(b[i]); if (U.size() == 1)U = "0" + U;
            int cnt = 0;
            if (U[0] == V[i][0])cnt++;
            if (U[1] == V[i][1])cnt++;
            c[cnt]++;
        }
        return make_tuple(c[0], c[1], c[2]);
    }
    if (Debug == 1) {
        for (int i = 0; i < 100; i++) {
            if (i)cout << " "; cout << V[i];
        }
        cout << endl;
        int V1, V2, V3; cin >> V1 >> V2 >> V3;
        return make_tuple(V1, V2, V3);
    }
}
void makerand() {
    bool uu[100];
    for (int i = 0; i < 100; i++)uu[i] = false;
    for (int j = 0; j < 100; j++) {
        while (true) {
            int H = rand() % 100;
            if (uu[H] == false) { b[j] = H; uu[H] = true; break; }
        }
    }
}
void query(int l, int r, int p, int x, int rec, vector<int>G) {
    if (l == r) {
        B.push_back(G[l]);
        return;
    }
    vector<string> R1, R2;
    for (int i = 0; i < 100; i++) {
        R1.push_back("??");
    }
    int m = (l + r) / 2;
    for (int i = G[l]; i <= G[m]; i++) {
        if (p == 0) R1[i][0] = (char)('0' + x);
        if (p == 1) R1[i][1] = (char)('0' + x);
    }
    tuple<int, int, int>A = Get(R1);
    int sums = get<1>(A) + get<2>(A) * 2;
    if (sums >= 1) query(l, m, p, x, sums, G);
    if (rec - sums >= 1)query(m + 1, r, p, x, rec - sums, G);
}
void solve2(vector<int>D, vector<int>C) {
    if (D.size() == 1) {
        a[C[0] * 2 + 1] = D[0];
        return;
    }
    vector<int>T[2];
    int mid = D.size() / 2;
    for (int i = 0; i < mid; i++) {
        vector<string>A;
        for (int j = 0; j < 100; j++)A.push_back("??");
        for (int j = 0; j < C.size(); j++) {
            if (j < mid)A[C[j]][1] = (char)('0' + D[2 * i]);
            else A[C[j]][1] = (char)('0' + D[2 * i + 1]);
        }
        tuple<int, int, int>S = Get(A);
        int SS = get<1>(S) + get<2>(S) * 2;
        if (SS == 0) { T[0].push_back(D[2 * i + 1]); T[1].push_back(D[2 * i]); }
        if (SS == 2) { T[0].push_back(D[2 * i]); T[1].push_back(D[2 * i + 1]); }
        if (SS == 1) {
            for (int j = 0; j < 100; j++)A[j] = "??";
            for (int j = 0; j < mid; j++)A[C[j]][1] = (char)('0' + (D[2 * i]));
            tuple<int, int, int>R = Get(A);
            int RR = get<1>(R) + get<2>(R) * 2;
            if (RR == 0) { T[1].push_back(D[2 * i + 1]); T[1].push_back(D[2 * i]); }
            if (RR == 1) { T[0].push_back(D[2 * i]); T[0].push_back(D[2 * i + 1]); }
        }
        if (T[0].size() == mid) {
            for (int j = 2 * (i + 1); j < D.size(); j++)T[1].push_back(D[j]);
            break;
        }
        if (T[1].size() == D.size() - mid) {
            for (int j = 2 * (i + 1); j < D.size(); j++)T[0].push_back(D[j]);
            break;
        }
    }
    vector<int>E1; for (int i = 0; i < mid; i++)E1.push_back(C[i]);
    vector<int>E2; for (int i = mid; i < C.size(); i++)E2.push_back(C[i]);
    solve2(T[0], E1);
    solve2(T[1], E2);
}
int main() {
    srand((unsigned)time(NULL));
    cin >> Q; makerand();
    int Target = rand() % 10;
    for (int i = 0; i < 200; i++)a[i] = Target;
    for (int i = 0; i < 1; i++) {
        for (int j = 0; j < 100; j++)used[j] = false;
        for (int j = 0; j < 10; j++) {
            if (j == Target)continue;
            vector<int>J;
            for (int k = 0; k < 100; k++) {
                if (used[k] == false)J.push_back(k);
            }
            B.clear();
            query(0, J.size() - 1, i, j, 10, J);
            for (int k = 0; k < B.size(); k++) {
                used[B[k]] = true; a[B[k] * 2 + i] = j;
            }
        }
    }
    for (int i = 0; i < 10; i++) {
        vector<int>F;
        for (int j = 0; j < 100; j++) {
            if (a[j * 2] == i)F.push_back(j);
        }
        solve2(vector<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, F);
    }
    for (int i = 0; i < 200; i++) {
        if (i >= 2 && i % 2 == 0)cout << " ";
        cout << a[i];
    }
    cout << endl;
    int V1, V2, V3; cin >> V1 >> V2 >> V3;
    if (Debug == 0) { cout << "#Queries = " << Queries + 1 << endl; }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0