oj.uz

Submission #248818

# Submission time Handle Problem Language Result Execution time Memory
248818 2020-07-13T13:29:49 Z tqbfjotld Password (RMI18_password) C++14
100 / 100
 961 ms 708 KB 
#include <bits/stdc++.h>
using namespace std;
int query(string str);

///editorial solution, based on quicksort?, s+n+nlogs supposedly
char ans[5005];
int N;
int tot_occ[128];

string repeat(char c, int n){
    string ret = "";
    for (int x = 0; x<n; x++){
        ret+=c;
    }
    return ret;
}

void rec(int l,int r,vector<pair<char,int> > chars){
    ///assume all subproblems to the left have been solved

    ///base case
    if (chars.size()==0) return;
    if (chars.size()==1){
            for (int x = l; x<l+chars[0].second; x++){
                ans[x] = chars[0].first;
            }
            return;
    }


    ///randomly choose character, use middle as pivot
    int pos = rand()%(chars.size());

    int occ = 0; ///occ-th occurrence of the character (0-index)
    char ch;
    int totalch;

    occ = chars[pos].second/2;
    ch = chars[pos].first;
    totalch = chars[pos].second;

    int occbef = 0; ///occurrences to the left of the subproblem
    for (int x = 0; x<l; x++){
        if (ans[x]==ch){
            occbef++;
        }
    }

    vector<pair<char,int> > lch,rch;
    for (auto x : chars){
        if (x.first==ch) continue;
        string qu = repeat(ch,occbef+occ+1);
        qu += repeat(x.first,N-qu.size());
        int res = query(qu);
        res -= occbef+occ+1;
        res = tot_occ[x.first]-res;
        for (int y = 0; y<l; y++){
            if (ans[y]==x.first) res--;
        }
        if (res>0){
            lch.push_back({x.first,res});
        }
        if (x.second-res>0){
            rch.push_back({x.first,x.second-res});
        }
    }
    if (occ>0){
        lch.push_back({ch,occ});
    }
    if (totalch-occ-1>0){
        rch.push_back({ch,totalch-occ-1});
    }
    int offset = 0;
    for (auto x : lch){
        offset += x.second;
    }
    rec(l,l+offset-1,lch);
    ans[l+offset] = ch;
    rec(l+offset+1,r,rch);
    return;

}

string guess(int n, int s){
    vector<pair<char,int> > chars;
    N = n;
    for (int x = 0; x<s; x++){
        string qu = repeat('a'+x,n);
        int t = query(qu);
        if (t>0){
            chars.push_back({'a'+x,t});
        }
        tot_occ['a'+x] = t;
    }
    rec(0,n-1,chars);
    string Ans = "";
    for (int x = 0; x<n; x++){
        Ans += ans[x];
    }
    return Ans;
}

Compilation message

password.cpp: In function 'void rec(int, int, std::vector<std::pair<char, int> >)':
password.cpp:57:30: warning: array subscript has type 'char' [-Wchar-subscripts]
         res = tot_occ[x.first]-res;
                              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 1 ms 380 KB Guessed the password with 107 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Guessed the password with 21 queries.
2 Correct 1 ms 256 KB Guessed the password with 44 queries.
3 Correct 0 ms 256 KB Guessed the password with 14 queries.
4 Correct 1 ms 256 KB Guessed the password with 102 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Guessed the password with 1482 queries.
2 Correct 38 ms 256 KB Guessed the password with 1730 queries.
3 Correct 67 ms 384 KB Guessed the password with 3024 queries.
4 Correct 117 ms 384 KB Guessed the password with 4785 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 1 ms 380 KB Guessed the password with 107 queries.
3 Correct 0 ms 256 KB Guessed the password with 21 queries.
4 Correct 1 ms 256 KB Guessed the password with 44 queries.
5 Correct 0 ms 256 KB Guessed the password with 14 queries.
6 Correct 1 ms 256 KB Guessed the password with 102 queries.
7 Correct 26 ms 384 KB Guessed the password with 1482 queries.
8 Correct 38 ms 256 KB Guessed the password with 1730 queries.
9 Correct 67 ms 384 KB Guessed the password with 3024 queries.
10 Correct 117 ms 384 KB Guessed the password with 4785 queries.
11 Correct 160 ms 388 KB Guessed the password with 5330 queries.
12 Correct 160 ms 504 KB Guessed the password with 5340 queries.
13 Correct 208 ms 384 KB Guessed the password with 6944 queries.
14 Correct 224 ms 384 KB Guessed the password with 7049 queries.
15 Correct 240 ms 384 KB Guessed the password with 7314 queries.
16 Correct 243 ms 384 KB Guessed the password with 7376 queries.
17 Correct 214 ms 384 KB Guessed the password with 6030 queries.
18 Correct 196 ms 388 KB Guessed the password with 5844 queries.
19 Correct 210 ms 384 KB Guessed the password with 6228 queries.
20 Correct 215 ms 384 KB Guessed the password with 6253 queries.
21 Correct 125 ms 388 KB Guessed the password with 3521 queries.
22 Correct 116 ms 384 KB Guessed the password with 3374 queries.

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Guessed the password with 68 queries.
2 Correct 1 ms 380 KB Guessed the password with 107 queries.
3 Correct 0 ms 256 KB Guessed the password with 21 queries.
4 Correct 1 ms 256 KB Guessed the password with 44 queries.
5 Correct 0 ms 256 KB Guessed the password with 14 queries.
6 Correct 1 ms 256 KB Guessed the password with 102 queries.
7 Correct 26 ms 384 KB Guessed the password with 1482 queries.
8 Correct 38 ms 256 KB Guessed the password with 1730 queries.
9 Correct 67 ms 384 KB Guessed the password with 3024 queries.
10 Correct 117 ms 384 KB Guessed the password with 4785 queries.
11 Correct 160 ms 388 KB Guessed the password with 5330 queries.
12 Correct 160 ms 504 KB Guessed the password with 5340 queries.
13 Correct 208 ms 384 KB Guessed the password with 6944 queries.
14 Correct 224 ms 384 KB Guessed the password with 7049 queries.
15 Correct 240 ms 384 KB Guessed the password with 7314 queries.
16 Correct 243 ms 384 KB Guessed the password with 7376 queries.
17 Correct 214 ms 384 KB Guessed the password with 6030 queries.
18 Correct 196 ms 388 KB Guessed the password with 5844 queries.
19 Correct 210 ms 384 KB Guessed the password with 6228 queries.
20 Correct 215 ms 384 KB Guessed the password with 6253 queries.
21 Correct 125 ms 388 KB Guessed the password with 3521 queries.
22 Correct 116 ms 384 KB Guessed the password with 3374 queries.
23 Correct 410 ms 608 KB Guessed the password with 8177 queries.
24 Correct 321 ms 568 KB Guessed the password with 6414 queries.
25 Correct 714 ms 640 KB Guessed the password with 14922 queries.
26 Correct 559 ms 652 KB Guessed the password with 11191 queries.
27 Correct 877 ms 708 KB Guessed the password with 17558 queries.
28 Correct 549 ms 404 KB Guessed the password with 10768 queries.
29 Correct 961 ms 452 KB Guessed the password with 19198 queries.
30 Correct 474 ms 648 KB Guessed the password with 9368 queries.