oj.uz

답안 #666329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
666329 2022-11-28T08:16:29 Z Nursik Password (RMI18_password) C++14
80 / 100
 1310 ms 624 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; --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];
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Guessed the password with 136 queries.
2 Correct 3 ms 208 KB Guessed the password with 300 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Guessed the password with 29 queries.
2 Correct 1 ms 208 KB Guessed the password with 35 queries.
3 Correct 1 ms 208 KB Guessed the password with 21 queries.
4 Correct 1 ms 304 KB Guessed the password with 94 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 208 KB Guessed the password with 2161 queries.
2 Correct 101 ms 304 KB Guessed the password with 8450 queries.
3 Correct 74 ms 316 KB Guessed the password with 3639 queries.
4 Correct 258 ms 336 KB Guessed the password with 12062 queries.

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Guessed the password with 136 queries.
2 Correct 3 ms 208 KB Guessed the password with 300 queries.
3 Correct 1 ms 208 KB Guessed the password with 29 queries.
4 Correct 1 ms 208 KB Guessed the password with 35 queries.
5 Correct 1 ms 208 KB Guessed the password with 21 queries.
6 Correct 1 ms 304 KB Guessed the password with 94 queries.
7 Correct 34 ms 208 KB Guessed the password with 2161 queries.
8 Correct 101 ms 304 KB Guessed the password with 8450 queries.
9 Correct 74 ms 316 KB Guessed the password with 3639 queries.
10 Correct 258 ms 336 KB Guessed the password with 12062 queries.
11 Correct 173 ms 336 KB Guessed the password with 6649 queries.
12 Correct 166 ms 384 KB Guessed the password with 6682 queries.
13 Correct 321 ms 460 KB Guessed the password with 15008 queries.
14 Correct 401 ms 336 KB Guessed the password with 15386 queries.
15 Correct 302 ms 460 KB Guessed the password with 11320 queries.
16 Correct 300 ms 464 KB Guessed the password with 11224 queries.
17 Correct 249 ms 344 KB Guessed the password with 8979 queries.
18 Correct 229 ms 336 KB Guessed the password with 9061 queries.
19 Correct 229 ms 340 KB Guessed the password with 7638 queries.
20 Correct 207 ms 344 KB Guessed the password with 7861 queries.
21 Correct 308 ms 336 KB Guessed the password with 11830 queries.
22 Correct 337 ms 336 KB Guessed the password with 11948 queries.

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Guessed the password with 136 queries.
2 Correct 3 ms 208 KB Guessed the password with 300 queries.
3 Correct 1 ms 208 KB Guessed the password with 29 queries.
4 Correct 1 ms 208 KB Guessed the password with 35 queries.
5 Correct 1 ms 208 KB Guessed the password with 21 queries.
6 Correct 1 ms 304 KB Guessed the password with 94 queries.
7 Correct 34 ms 208 KB Guessed the password with 2161 queries.
8 Correct 101 ms 304 KB Guessed the password with 8450 queries.
9 Correct 74 ms 316 KB Guessed the password with 3639 queries.
10 Correct 258 ms 336 KB Guessed the password with 12062 queries.
11 Correct 173 ms 336 KB Guessed the password with 6649 queries.
12 Correct 166 ms 384 KB Guessed the password with 6682 queries.
13 Correct 321 ms 460 KB Guessed the password with 15008 queries.
14 Correct 401 ms 336 KB Guessed the password with 15386 queries.
15 Correct 302 ms 460 KB Guessed the password with 11320 queries.
16 Correct 300 ms 464 KB Guessed the password with 11224 queries.
17 Correct 249 ms 344 KB Guessed the password with 8979 queries.
18 Correct 229 ms 336 KB Guessed the password with 9061 queries.
19 Correct 229 ms 340 KB Guessed the password with 7638 queries.
20 Correct 207 ms 344 KB Guessed the password with 7861 queries.
21 Correct 308 ms 336 KB Guessed the password with 11830 queries.
22 Correct 337 ms 336 KB Guessed the password with 11948 queries.
23 Execution timed out 1310 ms 624 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -