oj.uz

Submission #666326

# Submission time Handle Problem Language Result Execution time Memory
666326 2022-11-28T08:10:31 Z Nursik Password (RMI18_password) C++14
80 / 100
 1131 ms 456 KB 
#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define s second
#define f first
#define mp make_pair
 
int ix[30], adx[10000];
int query(string str);
string guess(int n, int s){
    string ans =  "";
    vector<pair<int, int>> vec;
    for (int i = 0; i < s; ++i){
        string kek = "";
        char ch = 'a';
        ch += i;
        for (int j = 1; j <= n; ++j){
            kek += ch;
        }
        ix[i] = query(kek);
        vec.pb(mp(ix[i], i));
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < s; ++i){
        int jj = vec[i].s;
        char ch = 'a';
        ch += jj;
        int len = 0;
        len = (int)ans.length();
        string nans = "";
        for (int j = 0; j <= len && ix[jj] > 0; ++j){
            string add = "";
            int is = 1;
            while (ix[jj] > 0){
                add += ch;
                string q = "";
                for (int k = 0; k < j; ++k){
                    q += ans[k];
                }
                q += add;
                for (int k = j; k < len; ++k){
                    q += ans[k];
                }
                if ((int)q.length() > n)
                    break;
                int kek = query(q);
                if (kek == len + is){
                    is += 1;
                    adx[j] += 1;
                    ix[jj] -= 1;
                }
                else{
                    break;
                }
            }
        }
        for (int j = 0; j <= len; ++j){
            while (adx[j] > 0){
                nans += ch;
                adx[j] -= 1;
            }
            if (j < len){
                nans += ans[j];
            }
        }
        ans = nans;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 73 queries.
2 Correct 1 ms 208 KB Guessed the password with 100 queries.
3 Correct 2 ms 208 KB Guessed the password with 93 queries.
4 Correct 2 ms 208 KB Guessed the password with 188 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 288 KB Guessed the password with 3135 queries.
2 Correct 116 ms 308 KB Guessed the password with 9219 queries.
3 Correct 67 ms 208 KB Guessed the password with 5203 queries.
4 Correct 205 ms 316 KB Guessed the password with 13859 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.
3 Correct 2 ms 208 KB Guessed the password with 73 queries.
4 Correct 1 ms 208 KB Guessed the password with 100 queries.
5 Correct 2 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 188 queries.
7 Correct 37 ms 288 KB Guessed the password with 3135 queries.
8 Correct 116 ms 308 KB Guessed the password with 9219 queries.
9 Correct 67 ms 208 KB Guessed the password with 5203 queries.
10 Correct 205 ms 316 KB Guessed the password with 13859 queries.
11 Correct 144 ms 300 KB Guessed the password with 9349 queries.
12 Correct 154 ms 312 KB Guessed the password with 9406 queries.
13 Correct 258 ms 304 KB Guessed the password with 17815 queries.
14 Correct 334 ms 316 KB Guessed the password with 18091 queries.
15 Correct 245 ms 312 KB Guessed the password with 14447 queries.
16 Correct 255 ms 308 KB Guessed the password with 14326 queries.
17 Correct 200 ms 436 KB Guessed the password with 12189 queries.
18 Correct 168 ms 340 KB Guessed the password with 12218 queries.
19 Correct 194 ms 300 KB Guessed the password with 10935 queries.
20 Correct 181 ms 436 KB Guessed the password with 11171 queries.
21 Correct 241 ms 440 KB Guessed the password with 15077 queries.
22 Correct 260 ms 456 KB Guessed the password with 15001 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 77 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.
3 Correct 2 ms 208 KB Guessed the password with 73 queries.
4 Correct 1 ms 208 KB Guessed the password with 100 queries.
5 Correct 2 ms 208 KB Guessed the password with 93 queries.
6 Correct 2 ms 208 KB Guessed the password with 188 queries.
7 Correct 37 ms 288 KB Guessed the password with 3135 queries.
8 Correct 116 ms 308 KB Guessed the password with 9219 queries.
9 Correct 67 ms 208 KB Guessed the password with 5203 queries.
10 Correct 205 ms 316 KB Guessed the password with 13859 queries.
11 Correct 144 ms 300 KB Guessed the password with 9349 queries.
12 Correct 154 ms 312 KB Guessed the password with 9406 queries.
13 Correct 258 ms 304 KB Guessed the password with 17815 queries.
14 Correct 334 ms 316 KB Guessed the password with 18091 queries.
15 Correct 245 ms 312 KB Guessed the password with 14447 queries.
16 Correct 255 ms 308 KB Guessed the password with 14326 queries.
17 Correct 200 ms 436 KB Guessed the password with 12189 queries.
18 Correct 168 ms 340 KB Guessed the password with 12218 queries.
19 Correct 194 ms 300 KB Guessed the password with 10935 queries.
20 Correct 181 ms 436 KB Guessed the password with 11171 queries.
21 Correct 241 ms 440 KB Guessed the password with 15077 queries.
22 Correct 260 ms 456 KB Guessed the password with 15001 queries.
23 Incorrect 1131 ms 420 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -