oj.uz

Submission #665801

# Submission time Handle Problem Language Result Execution time Memory
665801 2022-11-27T13:15:09 Z Nursik Password (RMI18_password) C++14
50 / 100
 1272 ms 412 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
 

int ix[30], adx[10000];
int query(string str);
string guess(int n, int s){
    string ans =  "";
    int mx = 0, c = -1;
    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);
        if (ix[i] > mx){
            mx = ix[i];
            c = i;
        }
    }
    for (int j = 1; j <= mx; ++j){
        char ch = 'a';
        ch += c;
        ans += ch;
    }
    ix[c] = 0;
    for (int i = 0; i < s; ++i){
        char ch = 'a';
        ch += i;
        int len = 0;
        len = (int)ans.length();
        string nans = "";
        for (int j = 0; j <= len && ix[i] > 0; ++j){
            string add = "";
            int is = 1;
            while (ix[i] > 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[i] -= 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 76 queries.
2 Correct 5 ms 208 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 53 queries.
2 Correct 2 ms 208 KB Guessed the password with 117 queries.
3 Correct 3 ms 208 KB Guessed the password with 181 queries.
4 Correct 2 ms 208 KB Guessed the password with 217 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 304 KB Guessed the password with 4789 queries.
2 Correct 134 ms 308 KB Guessed the password with 10282 queries.
3 Correct 212 ms 412 KB Guessed the password with 13668 queries.
4 Correct 270 ms 304 KB Guessed the password with 20690 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 5 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 217 queries.
7 Correct 62 ms 304 KB Guessed the password with 4789 queries.
8 Correct 134 ms 308 KB Guessed the password with 10282 queries.
9 Correct 212 ms 412 KB Guessed the password with 13668 queries.
10 Correct 270 ms 304 KB Guessed the password with 20690 queries.
11 Correct 1193 ms 328 KB Guessed the password with 49513 queries.
12 Correct 318 ms 296 KB Guessed the password with 19158 queries.
13 Correct 1085 ms 312 KB Guessed the password with 47684 queries.
14 Correct 408 ms 304 KB Guessed the password with 26327 queries.
15 Correct 982 ms 308 KB Guessed the password with 44836 queries.
16 Correct 443 ms 312 KB Guessed the password with 24337 queries.
17 Correct 1191 ms 308 KB Guessed the password with 49794 queries.
18 Correct 381 ms 312 KB Guessed the password with 24778 queries.
19 Execution timed out 1272 ms 308 KB Time limit exceeded (wall clock)
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 5 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 53 queries.
4 Correct 2 ms 208 KB Guessed the password with 117 queries.
5 Correct 3 ms 208 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 217 queries.
7 Correct 62 ms 304 KB Guessed the password with 4789 queries.
8 Correct 134 ms 308 KB Guessed the password with 10282 queries.
9 Correct 212 ms 412 KB Guessed the password with 13668 queries.
10 Correct 270 ms 304 KB Guessed the password with 20690 queries.
11 Correct 1193 ms 328 KB Guessed the password with 49513 queries.
12 Correct 318 ms 296 KB Guessed the password with 19158 queries.
13 Correct 1085 ms 312 KB Guessed the password with 47684 queries.
14 Correct 408 ms 304 KB Guessed the password with 26327 queries.
15 Correct 982 ms 308 KB Guessed the password with 44836 queries.
16 Correct 443 ms 312 KB Guessed the password with 24337 queries.
17 Correct 1191 ms 308 KB Guessed the password with 49794 queries.
18 Correct 381 ms 312 KB Guessed the password with 24778 queries.
19 Execution timed out 1272 ms 308 KB Time limit exceeded (wall clock)
20 Halted 0 ms 0 KB -