Submission #658596

#	Time	Username	Problem	Language	Result	Execution time	Memory
658596		NekoRolly	Password (RMI18_password)	C++17	100 / 100	617 ms	688 KiB

password

#include<bits/stdc++.h>
using namespace std;

int query(string s);

struct St{
	int t[26*4],cnt[26],n;
	string s;

	int op(int a,int b){ string s_ = s + char('a'+a);
		if (cnt[a] == 0) return b;
		if (cnt[b] == 0) return a;
		for (; s_.size()<n; ) s_ += char('a'+b);
		return query(s_) == s.size() + cnt[b] + 1 ? a : b;
	}

	void build(int id,int l,int r){
		if (l+1 == r){ string s_; t[id] = l;
			for (int i=0; i<n; i++) s_ += char('a'+l);
			cnt[l] = query(s_); return;
		}
		int m = (l+r)>>1;
		build(id<<1, l, m), build(id<<1|1, m, r);
		t[id] = op(t[id<<1], t[id<<1|1]);
	}

	void up(int id,int l,int r,int x){
		if (l+1 == r){ cnt[l]--; s += char('a'+l); return;}
		int m = (l+r)>>1;
		if (x < m) up(id<<1, l, m, x);
		else up(id<<1|1, m, r, x);
		t[id] = op(t[id<<1], t[id<<1|1]);
	}
} d;

string guess(int n,int m){
	d.n = n; d.build(1, 0, m);
	for (; n--; ) d.up(1, 0, m, d.t[1]);
	return d.s;
}

Compilation message (stderr)

password.cpp: In member function 'int St::op(int, int)':
password.cpp:13:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |   for (; s_.size()<n; ) s_ += char('a'+b);
      |          ~~~~~~~~~^~
password.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   return query(s_) == s.size() + cnt[b] + 1 ? a : b;
      |          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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