oj.uz

Submission #665610

# Submission time Handle Problem Language Result Execution time Memory
665610 2022-11-27T12:15:10 Z Nursik Password (RMI18_password) C++14
50 / 100
 1200 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
 

int ix[30], adx[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);
    }
    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 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 1 ms 208 KB Guessed the password with 73 queries.
2 Correct 2 ms 208 KB Guessed the password with 165 queries.
3 Correct 1 ms 208 KB Guessed the password with 103 queries.
4 Correct 2 ms 208 KB Guessed the password with 230 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 328 KB Guessed the password with 4582 queries.
2 Correct 125 ms 428 KB Guessed the password with 10304 queries.
3 Correct 167 ms 296 KB Guessed the password with 12562 queries.
4 Correct 290 ms 312 KB Guessed the password with 20502 queries.

Subtask #4
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 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 165 queries.
5 Correct 1 ms 208 KB Guessed the password with 103 queries.
6 Correct 2 ms 208 KB Guessed the password with 230 queries.
7 Correct 55 ms 328 KB Guessed the password with 4582 queries.
8 Correct 125 ms 428 KB Guessed the password with 10304 queries.
9 Correct 167 ms 296 KB Guessed the password with 12562 queries.
10 Correct 290 ms 312 KB Guessed the password with 20502 queries.
11 Incorrect 1200 ms 456 KB Could not guess the password with 50000 queries.
12 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 77 queries.
2 Correct 3 ms 208 KB Guessed the password with 188 queries.
3 Correct 1 ms 208 KB Guessed the password with 73 queries.
4 Correct 2 ms 208 KB Guessed the password with 165 queries.
5 Correct 1 ms 208 KB Guessed the password with 103 queries.
6 Correct 2 ms 208 KB Guessed the password with 230 queries.
7 Correct 55 ms 328 KB Guessed the password with 4582 queries.
8 Correct 125 ms 428 KB Guessed the password with 10304 queries.
9 Correct 167 ms 296 KB Guessed the password with 12562 queries.
10 Correct 290 ms 312 KB Guessed the password with 20502 queries.
11 Incorrect 1200 ms 456 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -