oj.uz

Submission #664277

# Submission time Handle Problem Language Result Execution time Memory
664277 2022-11-27T07:01:37 Z Nursik Password (RMI18_password) C++14
50 / 100
 1120 ms 484 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 is[30];
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 lol = "";
        char ch = 'a';
        ch += i;
        for (int j = 1; j <= n; ++j){
            lol += ch;
        }
        int kek = query(lol);
        if (kek > mx){
            mx = kek;
            c = i;
        }
        is[i] = kek;
    }
    for (int j = 1; j <= mx; ++j){
        char ch = 'a';
        ch += c;
        ans += ch;
    }
    is[c] = 0;
    for (int i = 0; i < s; ++i){
        if (is[i] == 0){
            continue;
        }
        while (is[i] > 0){
            char ch = 'a';
            ch += i;
            int len = (int)ans.size();
            int len2 = len;
            string nans = "", pref = "";
            for (int j = 0; j <= len; ++j){
                string suff = "";
                for (int k = j; k < len; ++k){
                    suff += ans[k];
                }
                while (is[i] > 0){
                    string q = nans;
                    q += ch;
                    q += suff;
                    if ((int)q.size() > n)
                        break;
                    int kek = query(q);
                    if (kek == len2 + 1){
                        nans += ch;
                        is[i] -= 1;
                        len2 += 1;
                    }
                    else{
                        break;
                    }
                }
                if (j < len){
                    nans += ans[j];
                    pref += 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 2 ms 208 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 52 queries.
2 Correct 2 ms 208 KB Guessed the password with 116 queries.
3 Correct 3 ms 300 KB Guessed the password with 181 queries.
4 Correct 2 ms 208 KB Guessed the password with 216 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 332 KB Guessed the password with 4788 queries.
2 Correct 132 ms 312 KB Guessed the password with 10281 queries.
3 Correct 194 ms 336 KB Guessed the password with 13667 queries.
4 Correct 306 ms 340 KB Guessed the password with 20689 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 2 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 3 ms 300 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 216 queries.
7 Correct 34 ms 332 KB Guessed the password with 4788 queries.
8 Correct 132 ms 312 KB Guessed the password with 10281 queries.
9 Correct 194 ms 336 KB Guessed the password with 13667 queries.
10 Correct 306 ms 340 KB Guessed the password with 20689 queries.
11 Correct 919 ms 484 KB Guessed the password with 49512 queries.
12 Correct 270 ms 468 KB Guessed the password with 19157 queries.
13 Correct 863 ms 356 KB Guessed the password with 47683 queries.
14 Correct 265 ms 340 KB Guessed the password with 26326 queries.
15 Correct 803 ms 460 KB Guessed the password with 44836 queries.
16 Correct 330 ms 464 KB Guessed the password with 24336 queries.
17 Execution timed out 1120 ms 464 KB Time limit exceeded (wall clock)
18 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 2 ms 208 KB Guessed the password with 187 queries.
3 Correct 2 ms 208 KB Guessed the password with 52 queries.
4 Correct 2 ms 208 KB Guessed the password with 116 queries.
5 Correct 3 ms 300 KB Guessed the password with 181 queries.
6 Correct 2 ms 208 KB Guessed the password with 216 queries.
7 Correct 34 ms 332 KB Guessed the password with 4788 queries.
8 Correct 132 ms 312 KB Guessed the password with 10281 queries.
9 Correct 194 ms 336 KB Guessed the password with 13667 queries.
10 Correct 306 ms 340 KB Guessed the password with 20689 queries.
11 Correct 919 ms 484 KB Guessed the password with 49512 queries.
12 Correct 270 ms 468 KB Guessed the password with 19157 queries.
13 Correct 863 ms 356 KB Guessed the password with 47683 queries.
14 Correct 265 ms 340 KB Guessed the password with 26326 queries.
15 Correct 803 ms 460 KB Guessed the password with 44836 queries.
16 Correct 330 ms 464 KB Guessed the password with 24336 queries.
17 Execution timed out 1120 ms 464 KB Time limit exceeded (wall clock)
18 Halted 0 ms 0 KB -