oj.uz

Submission #658596

# Submission time Handle Problem Language Result Execution time Memory
658596 2022-11-13T16:06:35 Z NekoRolly Password (RMI18_password) C++17
100 / 100
 617 ms 688 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Guessed the password with 59 queries.
2 Correct 1 ms 216 KB Guessed the password with 98 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 49 queries.
2 Correct 2 ms 208 KB Guessed the password with 91 queries.
3 Correct 3 ms 208 KB Guessed the password with 169 queries.
4 Correct 2 ms 208 KB Guessed the password with 197 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 320 KB Guessed the password with 3515 queries.
2 Correct 58 ms 320 KB Guessed the password with 4972 queries.
3 Correct 93 ms 312 KB Guessed the password with 6480 queries.
4 Correct 145 ms 320 KB Guessed the password with 8886 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Guessed the password with 59 queries.
2 Correct 1 ms 216 KB Guessed the password with 98 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 91 queries.
5 Correct 3 ms 208 KB Guessed the password with 169 queries.
6 Correct 2 ms 208 KB Guessed the password with 197 queries.
7 Correct 49 ms 320 KB Guessed the password with 3515 queries.
8 Correct 58 ms 320 KB Guessed the password with 4972 queries.
9 Correct 93 ms 312 KB Guessed the password with 6480 queries.
10 Correct 145 ms 320 KB Guessed the password with 8886 queries.
11 Correct 208 ms 420 KB Guessed the password with 12697 queries.
12 Correct 211 ms 432 KB Guessed the password with 13442 queries.
13 Correct 228 ms 328 KB Guessed the password with 13923 queries.
14 Correct 289 ms 328 KB Guessed the password with 14381 queries.
15 Correct 234 ms 456 KB Guessed the password with 14442 queries.
16 Correct 252 ms 332 KB Guessed the password with 14911 queries.
17 Correct 287 ms 332 KB Guessed the password with 14954 queries.
18 Correct 294 ms 328 KB Guessed the password with 16130 queries.
19 Correct 275 ms 336 KB Guessed the password with 15123 queries.
20 Correct 264 ms 460 KB Guessed the password with 15399 queries.
21 Correct 243 ms 340 KB Guessed the password with 15962 queries.
22 Correct 286 ms 336 KB Guessed the password with 16274 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Guessed the password with 59 queries.
2 Correct 1 ms 216 KB Guessed the password with 98 queries.
3 Correct 1 ms 208 KB Guessed the password with 49 queries.
4 Correct 2 ms 208 KB Guessed the password with 91 queries.
5 Correct 3 ms 208 KB Guessed the password with 169 queries.
6 Correct 2 ms 208 KB Guessed the password with 197 queries.
7 Correct 49 ms 320 KB Guessed the password with 3515 queries.
8 Correct 58 ms 320 KB Guessed the password with 4972 queries.
9 Correct 93 ms 312 KB Guessed the password with 6480 queries.
10 Correct 145 ms 320 KB Guessed the password with 8886 queries.
11 Correct 208 ms 420 KB Guessed the password with 12697 queries.
12 Correct 211 ms 432 KB Guessed the password with 13442 queries.
13 Correct 228 ms 328 KB Guessed the password with 13923 queries.
14 Correct 289 ms 328 KB Guessed the password with 14381 queries.
15 Correct 234 ms 456 KB Guessed the password with 14442 queries.
16 Correct 252 ms 332 KB Guessed the password with 14911 queries.
17 Correct 287 ms 332 KB Guessed the password with 14954 queries.
18 Correct 294 ms 328 KB Guessed the password with 16130 queries.
19 Correct 275 ms 336 KB Guessed the password with 15123 queries.
20 Correct 264 ms 460 KB Guessed the password with 15399 queries.
21 Correct 243 ms 340 KB Guessed the password with 15962 queries.
22 Correct 286 ms 336 KB Guessed the password with 16274 queries.
23 Correct 617 ms 688 KB Guessed the password with 23565 queries.
24 Correct 578 ms 480 KB Guessed the password with 22882 queries.
25 Correct 563 ms 540 KB Guessed the password with 23759 queries.
26 Correct 567 ms 524 KB Guessed the password with 23460 queries.
27 Correct 590 ms 536 KB Guessed the password with 23800 queries.
28 Correct 562 ms 620 KB Guessed the password with 22182 queries.
29 Correct 592 ms 544 KB Guessed the password with 23809 queries.
30 Correct 509 ms 588 KB Guessed the password with 21105 queries.