結果
問題 | No.2848 Birthday Hit and Blow |
ユーザー | kotatsugame |
提出日時 | 2024-08-23 22:21:37 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 115 ms / 2,000 ms |
コード長 | 2,323 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 95,492 KB |
実行使用メモリ | 24,836 KB |
平均クエリ数 | 448.00 |
最終ジャッジ日時 | 2024-08-23 22:21:40 |
合計ジャッジ時間 | 2,321 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
24,812 KB |
testcase_01 | AC | 115 ms
24,836 KB |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<map> #include<cassert> #include<cstdlib> using namespace std; //vector<string>asked; pair<int,int>calc(string SQ,string SA) { int idx[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; idx[SA[0]-'0']=0; idx[SA[1]-'0']=1; idx[SA[2]-'0']=2; idx[SA[3]-'0']=3; int H=0,B=0; for(int i=0;i<4;i++) { int j=idx[SQ[i]-'0']; if(j==i)H++; else if(j>=0)B++; } /* for(int i=0;i<4;i++) { if(SQ[i]==SA[i])H++; for(int j=0;j<4;j++)if(i!=j&&SQ[i]==SA[j])B++; } */ return make_pair(H,B); } string ans; vector<string>SQs; void dfs(vector<string>SAs,int t) { if(SAs.size()==1) { //output cout<<"! "<<SAs[0]<<endl; int a;cin>>a;if(a==-1)exit(0); return; } assert(t<6); int mx_min=1e9; string SSQ; for(string SQ:SQs) { map<pair<int,int>,vector<string> >mp; int mx=0; for(string SA:SAs) { auto p=calc(SQ,SA); mp[p].push_back(SA); mx=max(mx,(int)mp[p].size()); } if(mx_min>mx) { mx_min=mx; SSQ=SQ; } } //asked.push_back(SSQ); cout<<"? "<<SSQ<<endl; pair<int,int>ret; cin>>ret.first>>ret.second; //ret=calc(SSQ,ans); vector<string>nSAs; for(string SA:SAs)if(calc(SSQ,SA)==ret)nSAs.push_back(SA); dfs(nSAs,t+1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); if(false) { for(int v=0;v<=9999;v++) { string t=""; t+=v/1000+'0'; t+=v/100%10+'0'; t+=v/10%10+'0'; t+=v%10+'0'; string st=t; sort(st.begin(),st.end()); if(st[0]!=st[1]&&st[1]!=st[2]&&st[2]!=st[3])SQs.push_back(t); } assert(SQs.size()==10*9*8*7); } SQs={"0123","0124","0125","0126","0128","0145","0148","0167","0168","0178","0214","0415","0456","0467","0567","0617","0718","2567","4156","4325",}; vector<string>SAs; { for(int M=1;M<=12;M++) { int L=M==2?29:L==4||L==6||L==9||L==11?30:31; for(int D=1;D<=L;D++) { string t=""; t+=M/10+'0'; t+=M%10+'0'; t+=D/10+'0'; t+=D%10+'0'; string st=t; sort(st.begin(),st.end()); if(st[0]!=st[1]&&st[1]!=st[2]&&st[2]!=st[3])SAs.push_back(t); } } } int T;cin>>T; for(;T--;) { //cin>>ans; dfs(SAs,0); } /* sort(asked.begin(),asked.end()); asked.erase(unique(asked.begin(),asked.end()),asked.end()); cout<<"{"; for(string t:asked)cout<<'"'<<t<<'"'<<","; cout<<"}"<<endl; cout<<asked.size()<<endl; */ }