oj.uz

답안 #642887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642887 2022-09-20T17:26:20 Z SlavicG Password (RMI18_password) C++17
80 / 100
 701 ms 560 KB 
#include "bits/stdc++.h"
using namespace std;
int query(string str);

#define sz(a) (int)a.size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string guess(int n, int s) {
    vector<pair<int, char>> v;
    for(int f = 0; f < s; ++f) {
        char c = char('a' + f);
        string paiu = string(n, c);
        int x = query(paiu);
        if(x > 0) {
            v.push_back({x, c});
        }
    }
    assert(v.size() > 0);
    sort(v.begin(), v.end());
    string ans = string(v[0].first, v[0].second);
    v.erase(v.begin());

    assert(sz(ans) > 0);
    if(!sz(v)) return ans;


    for(auto noo: v) {
        char c = noo.second;
        int cnt = noo.first;
        string ff = ans;
        string bruh = "";
        for(int i = 0; i <= sz(ff); ++i) {
            int lol = 0, l = 1, r = cnt;
            string rem = bruh;
            if(cnt >= 5) {
                int mid = 5;
                bruh = rem;
                for(int j = 0; j < mid; ++j) bruh += c;
                for(int k = i; k < sz(ff); ++k) {
                    bruh += ff[k];
                }
                if(query(bruh) == sz(bruh)) {
                    lol = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            bruh = rem;
            while(l <= r) {
                int mid = l + r >> 1;
                bruh = rem;
                for(int j = 0; j < mid; ++j) bruh += c;
                for(int k = i; k < sz(ff); ++k) {
                    bruh += ff[k];
                }

                if(query(bruh) == sz(bruh)) {
                    lol = mid;
                    l = mid + 1;
                } else r = mid - 1;
            }
            cnt -= lol;
            bruh = rem;
            for(int j = 0; j < lol; ++j) bruh += c;
            if(i < sz(ff)) bruh += ff[i];
        }
        ans = bruh;
    }
    return ans;
}

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:49:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |                 int mid = l + r >> 1;
      |                           ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 50 queries.
2 Correct 2 ms 228 KB Guessed the password with 96 queries.
3 Correct 1 ms 208 KB Guessed the password with 15 queries.
4 Correct 4 ms 208 KB Guessed the password with 265 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 312 KB Guessed the password with 6500 queries.
2 Correct 276 ms 284 KB Guessed the password with 21804 queries.
3 Correct 88 ms 424 KB Guessed the password with 10792 queries.
4 Correct 378 ms 336 KB Guessed the password with 34818 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 50 queries.
4 Correct 2 ms 228 KB Guessed the password with 96 queries.
5 Correct 1 ms 208 KB Guessed the password with 15 queries.
6 Correct 4 ms 208 KB Guessed the password with 265 queries.
7 Correct 56 ms 312 KB Guessed the password with 6500 queries.
8 Correct 276 ms 284 KB Guessed the password with 21804 queries.
9 Correct 88 ms 424 KB Guessed the password with 10792 queries.
10 Correct 378 ms 336 KB Guessed the password with 34818 queries.
11 Correct 278 ms 336 KB Guessed the password with 19680 queries.
12 Correct 293 ms 336 KB Guessed the password with 19786 queries.
13 Correct 614 ms 428 KB Guessed the password with 44078 queries.
14 Correct 701 ms 436 KB Guessed the password with 44862 queries.
15 Correct 479 ms 348 KB Guessed the password with 33667 queries.
16 Correct 474 ms 348 KB Guessed the password with 33252 queries.
17 Correct 367 ms 432 KB Guessed the password with 26581 queries.
18 Correct 362 ms 448 KB Guessed the password with 27010 queries.
19 Correct 266 ms 420 KB Guessed the password with 22738 queries.
20 Correct 377 ms 468 KB Guessed the password with 23456 queries.
21 Correct 398 ms 468 KB Guessed the password with 34686 queries.
22 Correct 559 ms 460 KB Guessed the password with 34270 queries.

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 76 queries.
2 Correct 4 ms 208 KB Guessed the password with 187 queries.
3 Correct 1 ms 208 KB Guessed the password with 50 queries.
4 Correct 2 ms 228 KB Guessed the password with 96 queries.
5 Correct 1 ms 208 KB Guessed the password with 15 queries.
6 Correct 4 ms 208 KB Guessed the password with 265 queries.
7 Correct 56 ms 312 KB Guessed the password with 6500 queries.
8 Correct 276 ms 284 KB Guessed the password with 21804 queries.
9 Correct 88 ms 424 KB Guessed the password with 10792 queries.
10 Correct 378 ms 336 KB Guessed the password with 34818 queries.
11 Correct 278 ms 336 KB Guessed the password with 19680 queries.
12 Correct 293 ms 336 KB Guessed the password with 19786 queries.
13 Correct 614 ms 428 KB Guessed the password with 44078 queries.
14 Correct 701 ms 436 KB Guessed the password with 44862 queries.
15 Correct 479 ms 348 KB Guessed the password with 33667 queries.
16 Correct 474 ms 348 KB Guessed the password with 33252 queries.
17 Correct 367 ms 432 KB Guessed the password with 26581 queries.
18 Correct 362 ms 448 KB Guessed the password with 27010 queries.
19 Correct 266 ms 420 KB Guessed the password with 22738 queries.
20 Correct 377 ms 468 KB Guessed the password with 23456 queries.
21 Correct 398 ms 468 KB Guessed the password with 34686 queries.
22 Correct 559 ms 460 KB Guessed the password with 34270 queries.
23 Incorrect 663 ms 560 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -