oj.uz

Submission #251386

# Submission time Handle Problem Language Result Execution time Memory
251386 2020-07-21T05:00:28 Z lyc Password (RMI18_password) C++14
30 / 100
 465 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SZ(x) ((int)(x).size())
typedef pair<int,int> ii;

int query(string str);

int N;
const int mxS = 26;
char alpha[mxS];

string guess(int _N, int S) {
	N = _N;
	FOR(i,0,S-1) alpha[i] = 'a' + i;
	
	vector<ii> freq;
	FOR(i,0,S-1) {
		string s(N,alpha[i]);
		int f = query(s);
		freq.emplace_back(f,i);
		//~ cout << f << ' ';
	}
	//~ cout << endl;
	
	string s(freq[0].first,alpha[freq[0].second]);
	FOR(i,1,SZ(freq)-1){
		FOR(j,1,freq[i].first){
			FOR(k,0,SZ(s)){
				string t = s.substr(0,k) + alpha[freq[i].second] + s.substr(k);
				int x = query(t);
				if (x == SZ(t)) { s = t; break; }
			}
		}
		//TRACE(s);
	}
	
	return s;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Guessed the password with 451 queries.
2 Correct 11 ms 256 KB Guessed the password with 716 queries.
3 Correct 2 ms 256 KB Guessed the password with 103 queries.
4 Correct 43 ms 256 KB Guessed the password with 2941 queries.

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 256 KB Could not guess the password with 50000 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 451 queries.
4 Correct 11 ms 256 KB Guessed the password with 716 queries.
5 Correct 2 ms 256 KB Guessed the password with 103 queries.
6 Correct 43 ms 256 KB Guessed the password with 2941 queries.
7 Incorrect 465 ms 256 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Guessed the password with 76 queries.
2 Correct 2 ms 256 KB Guessed the password with 187 queries.
3 Correct 5 ms 256 KB Guessed the password with 451 queries.
4 Correct 11 ms 256 KB Guessed the password with 716 queries.
5 Correct 2 ms 256 KB Guessed the password with 103 queries.
6 Correct 43 ms 256 KB Guessed the password with 2941 queries.
7 Incorrect 465 ms 256 KB Could not guess the password with 50000 queries.
8 Halted 0 ms 0 KB -