Submission #1162615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162615		cnn008	Password (RMI18_password)	C++17	0 / 100	33 ms	436 KiB

password

#include "bits/stdc++.h"
using namespace std;
int query(string p);
string guess(int n, int s){
    string ans;
    vector <int> cnt(s,0);
    for(int i=0; i<s; i++){
      char c=char('a'+i);
      string cur;
      while((int)cur.size()<n){
        cur.push_back(c);
        if(query(cur)!=(int)cur.size()){
          cur.pop_back();
          break;  
        }
      }
      cnt[i]=(int)cur.size();
    }
    int st=-1;
    for(int i=0; i<s; i++){
      if(cnt[i]){
        char c=char(i+'a');
        for(int j=0; j<cnt[i]; j++) ans.push_back(c);
        st=i;
        break;
      }
    }
    auto ck = [&](char c, int l) ->bool{
      string t;
      t.push_back(c);
      for(int i=0; i<(int)ans.size()-1-l+1; i++) if(ans[i]==c) t.push_back(c);
      for(int i=(int)ans.size()-1-l+1; i<(int)ans.size(); i++) t.push_back(ans[i]);
      return (query(t)==(int)t.size());
    };
    for(int i=st+1; i<s; i++){
      for(int j=0; j<cnt[i]; j++){
        char c=char('a'+i);
        int l=1,r=(int)ans.size(),cc=0;
        while(l<=r){
          int mid=(l+r)>>1;
          if(ck(c,mid)){
            cc=mid;
            l=mid+1;
          }else r=mid-1;
        }
        string _ans;
        for(int i=(int)ans.size()-1; i>=(int)ans.size()-1-cc+1; i--) _ans.push_back(ans[i]);
        _ans.push_back(c);
        for(int i=(int)ans.size()-1-cc+1-1; i>=0; i--) _ans.push_back(ans[i]);
        reverse(_ans.begin(),_ans.end());
        ans.swap(_ans);
      }
    }
    assert((int)ans.size()==n);
    return ans;
  }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20