oj.uz

Submission #666330

# Submission time Handle Problem Language Result Execution time Memory
666330 2022-11-28T08:19:01 Z Nursik Password (RMI18_password) C++14
80 / 100
 1326 ms 576 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 mp make_pair
#define f first
#define s second

int ix[30], adx[10000], lst[10000];
char y[10000];
int query(string str);
string guess(int n, int s){
    string ans =  "";
    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);
    }
    vector<pair<int, int>> vv;
    for (int i = 0; i < s; ++i){
        vv.pb(mp(ix[i], i));
    }
    sort(vv.begin(), vv.end());
    for (int i = 0; i < s; ++i){
        int jj = vv[i].s;
        if (ix[jj] == 0){
            continue;
        }
        char ch = 'a';
        ch += jj;
        string nans = "";
        for (int j = 0; j < n; ++j){
            if (j < (int)ans.size()){
                y[j] = ans[j];
            }
            else{
                y[j] = ch;
            }
        }
        for (int j = (int)ans.size(); j >= 0 && ix[jj] > 0; --j){
            string q = "";
            for (int k = 0; k < n; ++k){
                if (k < j){
                    q += ans[k];
                }
                else{
                    q += ch;
                }
            }
            int kek = query(q);
            kek -= j;
            adx[j] = kek - lst[j + 1];
            lst[j] = lst[j + 1] + adx[j];
            ix[jj] -= adx[j];
        }
        for (int j = 0; j <= (int)ans.size(); ++j){
            while (adx[j] > 0){
                nans += ch;
                adx[j] -= 1;
            }
            if (j < (int)ans.size()){
                nans += ans[j];
            }
        }
        for (int j = 0; j < n; ++j){
            lst[j] = 0, adx[j] = 0;
        }
        ans = nans;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Guessed the password with 29 queries.
2 Correct 1 ms 208 KB Guessed the password with 35 queries.
3 Correct 0 ms 208 KB Guessed the password with 21 queries.
4 Correct 2 ms 208 KB Guessed the password with 88 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 208 KB Guessed the password with 2149 queries.
2 Correct 146 ms 308 KB Guessed the password with 8343 queries.
3 Correct 71 ms 312 KB Guessed the password with 3614 queries.
4 Correct 212 ms 336 KB Guessed the password with 11949 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 89 queries.
2 Correct 2 ms 208 KB Guessed the password with 158 queries.
3 Correct 1 ms 304 KB Guessed the password with 29 queries.
4 Correct 1 ms 208 KB Guessed the password with 35 queries.
5 Correct 0 ms 208 KB Guessed the password with 21 queries.
6 Correct 2 ms 208 KB Guessed the password with 88 queries.
7 Correct 30 ms 208 KB Guessed the password with 2149 queries.
8 Correct 146 ms 308 KB Guessed the password with 8343 queries.
9 Correct 71 ms 312 KB Guessed the password with 3614 queries.
10 Correct 212 ms 336 KB Guessed the password with 11949 queries.
11 Correct 146 ms 336 KB Guessed the password with 6578 queries.
12 Correct 167 ms 340 KB Guessed the password with 6602 queries.
13 Correct 367 ms 336 KB Guessed the password with 14901 queries.
14 Correct 375 ms 336 KB Guessed the password with 15295 queries.
15 Correct 293 ms 336 KB Guessed the password with 11242 queries.
16 Correct 281 ms 464 KB Guessed the password with 11154 queries.
17 Correct 197 ms 344 KB Guessed the password with 8889 queries.
18 Correct 257 ms 336 KB Guessed the password with 8948 queries.
19 Correct 206 ms 344 KB Guessed the password with 7574 queries.
20 Correct 203 ms 340 KB Guessed the password with 7791 queries.
21 Correct 336 ms 436 KB Guessed the password with 11684 queries.
22 Correct 348 ms 456 KB Guessed the password with 11773 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Guessed the password with 89 queries.
2 Correct 2 ms 208 KB Guessed the password with 158 queries.
3 Correct 1 ms 304 KB Guessed the password with 29 queries.
4 Correct 1 ms 208 KB Guessed the password with 35 queries.
5 Correct 0 ms 208 KB Guessed the password with 21 queries.
6 Correct 2 ms 208 KB Guessed the password with 88 queries.
7 Correct 30 ms 208 KB Guessed the password with 2149 queries.
8 Correct 146 ms 308 KB Guessed the password with 8343 queries.
9 Correct 71 ms 312 KB Guessed the password with 3614 queries.
10 Correct 212 ms 336 KB Guessed the password with 11949 queries.
11 Correct 146 ms 336 KB Guessed the password with 6578 queries.
12 Correct 167 ms 340 KB Guessed the password with 6602 queries.
13 Correct 367 ms 336 KB Guessed the password with 14901 queries.
14 Correct 375 ms 336 KB Guessed the password with 15295 queries.
15 Correct 293 ms 336 KB Guessed the password with 11242 queries.
16 Correct 281 ms 464 KB Guessed the password with 11154 queries.
17 Correct 197 ms 344 KB Guessed the password with 8889 queries.
18 Correct 257 ms 336 KB Guessed the password with 8948 queries.
19 Correct 206 ms 344 KB Guessed the password with 7574 queries.
20 Correct 203 ms 340 KB Guessed the password with 7791 queries.
21 Correct 336 ms 436 KB Guessed the password with 11684 queries.
22 Correct 348 ms 456 KB Guessed the password with 11773 queries.
23 Execution timed out 1326 ms 576 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -