結果
| 問題 | No.2848 Birthday Hit and Blow |
| ユーザー |
 tko919
|
| 提出日時 | 2024-06-13 14:01:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,304 bytes |
| コンパイル時間 | 2,396 ms |
| コンパイル使用メモリ | 209,332 KB |
| 最終ジャッジ日時 | 2025-02-21 21:28:57 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | TLE * 1 |
ソースコード
// #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#endiftemplate <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;}