#988212 (C++17) No.2848 Birthday Hit and Blow

提出ソース
結果

問題	No.2848 Birthday Hit and Blow
ユーザー	tko919
提出日時	2024-06-13 14:01:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	10,304 bytes
コンパイル時間	2,609 ms
コンパイル使用メモリ	218,132 KB
実行使用メモリ	40,396 KB
平均クエリ数	2.50
最終ジャッジ日時	2024-07-17 02:36:29
合計ジャッジ時間	5,957 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	48 ms 24,556 KB
testcase_01	TLE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rrep(i,a,b) for(int i=(int)(b-1);i>=(int)(a);i--)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin())
#define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin())

using ll=long long int;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;

template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<typename T,typename U>T ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>T floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);}
template<typename T>int popcnt(T x){return __builtin_popcountll(x);}
template<typename T>int topbit(T x){return (x==0?-1:63-__builtin_clzll(x));}
template<typename T>int lowbit(T x){return (x==0?-1:__builtin_ctzll(x));}
// #line 2 "library/Utility/fastio.hpp"
// #include <unistd.h>
// namespace fastio {
// static constexpr uint32_t SZ = 1 << 17;
// char ibuf[SZ];
// char obuf[SZ];
// char out[100];
// // pointer of ibuf, obuf

// uint32_t pil = 0, pir = 0, por = 0;

// struct Pre {
//     char num[10000][4];
//     constexpr Pre() : num() {
//         for (int i = 0; i < 10000; i++) {
//             int n = i;
//             for (int j = 3; j >= 0; j--) {
//                 num[i][j] = n % 10 | '0';
//                 n /= 10;
//             }
//         }
//     }
// } constexpr pre;

// inline void load() {
//     memmove(ibuf, ibuf + pil, pir - pil);
//     pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
//     pil = 0;
//     if (pir < SZ)
//         ibuf[pir++] = '\n';
// }

// inline void flush() {
//     fwrite(obuf, 1, por, stdout);
//     por = 0;
// }

// void rd(char &c) {
//     do {
//         if (pil + 1 > pir)
//             load();
//         c = ibuf[pil++];
//     } while (isspace(c));
// }

// void rd(string &x) {
//     x.clear();
//     char c;
//     do {
//         if (pil + 1 > pir)
//             load();
//         c = ibuf[pil++];
//     } while (isspace(c));
//     do {
//         x += c;
//         if (pil == pir)
//             load();
//         c = ibuf[pil++];
//     } while (!isspace(c));
// }

// template <typename T> void rd_real(T &x) {
//     string s;
//     rd(s);
//     x = stod(s);
// }

// template <typename T> void rd_integer(T &x) {
//     if (pil + 100 > pir)
//         load();
//     char c;
//     do
//         c = ibuf[pil++];
//     while (c < '-');
//     bool minus = 0;
//     if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
//         if (c == '-') {
//             minus = 1, c = ibuf[pil++];
//         }
//     }
//     x = 0;
//     while ('0' <= c) {
//         x = x * 10 + (c & 15), c = ibuf[pil++];
//     }
//     if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
//         if (minus)
//             x = -x;
//     }
// }

// void rd(int &x) {
//     rd_integer(x);
// }
// void rd(ll &x) {
//     rd_integer(x);
// }
// void rd(i128 &x) {
//     rd_integer(x);
// }
// void rd(uint &x) {
//     rd_integer(x);
// }
// void rd(ull &x) {
//     rd_integer(x);
// }
// void rd(u128 &x) {
//     rd_integer(x);
// }
// void rd(double &x) {
//     rd_real(x);
// }
// void rd(long double &x) {
//     rd_real(x);
// }

// template <class T, class U> void rd(pair<T, U> &p) {
//     return rd(p.first), rd(p.second);
// }
// template <size_t N = 0, typename T> void rd_tuple(T &t) {
//     if constexpr (N < std::tuple_size<T>::value) {
//         auto &x = std::get<N>(t);
//         rd(x);
//         rd_tuple<N + 1>(t);
//     }
// }
// template <class... T> void rd(tuple<T...> &tpl) {
//     rd_tuple(tpl);
// }

// template <size_t N = 0, typename T> void rd(array<T, N> &x) {
//     for (auto &d : x)
//         rd(d);
// }
// template <class T> void rd(vector<T> &x) {
//     for (auto &d : x)
//         rd(d);
// }

// void read() {}
// template <class H, class... T> void read(H &h, T &...t) {
//     rd(h), read(t...);
// }

// void wt(const char c) {
//     if (por == SZ)
//         flush();
//     obuf[por++] = c;
// }
// void wt(const string s) {
//     for (char c : s)
//         wt(c);
// }
// void wt(const char *s) {
//     size_t len = strlen(s);
//     for (size_t i = 0; i < len; i++)
//         wt(s[i]);
// }

// template <typename T> void wt_integer(T x) {
//     if (por > SZ - 100)
//         flush();
//     if (x < 0) {
//         obuf[por++] = '-', x = -x;
//     }
//     int outi;
//     for (outi = 96; x >= 10000; outi -= 4) {
//         memcpy(out + outi, pre.num[x % 10000], 4);
//         x /= 10000;
//     }
//     if (x >= 1000) {
//         memcpy(obuf + por, pre.num[x], 4);
//         por += 4;
//     } else if (x >= 100) {
//         memcpy(obuf + por, pre.num[x] + 1, 3);
//         por += 3;
//     } else if (x >= 10) {
//         int q = (x * 103) >> 10;
//         obuf[por] = q | '0';
//         obuf[por + 1] = (x - q * 10) | '0';
//         por += 2;
//     } else
//         obuf[por++] = x | '0';
//     memcpy(obuf + por, out + outi + 4, 96 - outi);
//     por += 96 - outi;
// }

// template <typename T> void wt_real(T x) {
//     ostringstream oss;
//     oss << fixed << setprecision(15) << double(x);
//     string s = oss.str();
//     wt(s);
// }

// void wt(int x) {
//     wt_integer(x);
// }
// void wt(ll x) {
//     wt_integer(x);
// }
// void wt(i128 x) {
//     wt_integer(x);
// }
// void wt(unsigned int x) {
//     wt_integer(x);
// }
// void wt(ull x) {
//     wt_integer(x);
// }
// void wt(u128 x) {
//     wt_integer(x);
// }
// void wt(double x) {
//     wt_real(x);
// }
// void wt(long double x) {
//     wt_real(x);
// }

// template <class T, class U> void wt(const pair<T, U> val) {
//     wt(val.first);
//     wt(' ');
//     wt(val.second);
// }
// template <size_t N = 0, typename T> void wt_tuple(const T t) {
//     if constexpr (N < std::tuple_size<T>::value) {
//         if constexpr (N > 0) {
//             wt(' ');
//         }
//         const auto x = std::get<N>(t);
//         wt(x);
//         wt_tuple<N + 1>(t);
//     }
// }
// template <class... T> void wt(tuple<T...> tpl) {
//     wt_tuple(tpl);
// }
// template <class T, size_t S> void wt(const array<T, S> val) {
//     auto n = val.size();
//     for (size_t i = 0; i < n; i++) {
//         if (i)
//             wt(' ');
//         wt(val[i]);
//     }
// }
// template <class T> void wt(const vector<T> val) {
//     auto n = val.size();
//     for (size_t i = 0; i < n; i++) {
//         if (i)
//             wt(' ');
//         wt(val[i]);
//     }
// }

// void print() {
//     wt('\n');
// }
// template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
//     wt(head);
//     if (sizeof...(Tail))
//         wt(' ');
//     print(forward<Tail>(tail)...);
// }
// void __attribute__((destructor)) _d() {
//     flush();
// }
// } // namespace fastio

// using fastio::flush;
// using fastio::print;
// using fastio::read;

#ifdef LOCAL
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define show(...) true
#endif
template <typename T> void _show(int i, T name) {
    cerr << '\n';
}
template <typename T1, typename T2, typename... T3>
void _show(int i, const T1 &a, const T2 &b, const T3 &...c) {
    for (; a[i] != ',' && a[i] != '\0'; i++)
        cerr << a[i];
    cerr << ":" << b << " ";
    _show(i + 1, a, c...);
}
// template <class T, class U>
// ostream &operator<<(ostream &os, const pair<T, U> &p) {
//     os << "P(" << p.first << ", " << p.second << ")";
//     return os;
// }
// template <typename T, template <class> class C>
// ostream &operator<<(ostream &os, const C<T> &v) {
//     os << "[";
//     for (auto d : v)
//         os << d << ", ";
//     os << "]";
//     return os;
// }

int month[]={-1,31,29,31,30,31,30,31,31,30,31,30,31};
using P=pair<int,int>;

P ask(string& s){
    cout<<"? "<<s<<endl;
    int H,B;
    cin>>H>>B;
    assert(H!=-1);
    return {H,B};
}

void solve(){
    vector<string> cand;
    rep(mm,1,13){
        rep(dd,1,month[mm]+1){
            string add;
            if(mm<=9)add+="0";
            add+=to_string(mm);
            if(dd<=9)add+="0";
            add+=to_string(dd);
            cand.push_back(add);
        }
    }

    auto HitBlow=[&](string& s,string& t)->P{
        int num[10]={};
        int H=0,B=0;
        rep(i,0,4)if(s[i]==t[i])H++;
        rep(i,0,4)num[s[i]-'0']++;
        rep(i,0,4)B+=num[t[i]-'0'];
        B-=H;
        return {H,B};
    };

    auto best=[&]()->string{
        int score=inf;
        string ret;
        rep(x,0,10){
            rep(y,0,10)if(x!=y){
                rep(z,0,10)if(x!=z and y!=z){
                    rep(w,0,10)if(x!=w and y!=w and z!=w){
                        string que=to_string(1000*x+100*y+10*z+w);
                        while(SZ(que)<4)que.insert(que.begin(),'0');
                        map<P,vector<string>> cur;
                        for(auto& c:cand)cur[HitBlow(que,c)].push_back(c);
                        int mx=0;
                        for(auto& [_,cs]:cur)chmax(mx,SZ(cs));
                        if(chmin(score,mx)){
                            ret=que;
                        }
                    }
                }
            }
        }
        return ret;
    };

    auto squeeze=[&](string& s,P HB)->void{
        vector<string> nxt;
        for(auto& c:cand){
            if(HitBlow(s,c)==HB){
                nxt.push_back(c);
            }
        }
        swap(cand,nxt);
    };

    string start="4521";
    P HB=ask(start);
    squeeze(start,HB);
    show(SZ(cand));
    while(SZ(cand)>1){
        string s=best();
        HB=ask(s);
        squeeze(s,HB);
    }
    assert(SZ(cand)==1);
    cout<<"! "<<cand[0]<<endl;
    int ret;
    cin>>ret;
    assert(ret==0);
}

int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}
yukicoder

結果

テストケース

ソースコード
