oj.uz

답안 #1118525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1118525 2024-11-25T15:45:12 Z somefolk Password (RMI18_password) C++17
50 / 100
 1008 ms 740 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
#include <cassert>
using namespace std;

#define endl "\n"
// #define int long long

const int INF = 2 * 1e5 + 5;
const int MOD = 1e9 + 7;

// int query(string s){
//     int n;
//     cout << s;
//     cin >> n;
//     return n;
// }

int query(string s);

string guess(int n, int s){
    bool pass = false;
    string sol = "";
    for(char i = 'a'; i < 'a'+s; i++){
        string letter = string(n, i);
        int amount = query(letter);
        int initAmount = amount, totalDiff = 0;
        if(amount == 0) continue;
        if(!pass){
            sol += string(amount, i);
            pass = true;
        } else {
            int len = sol.length();
            vector<pair<int, int>> add;
            for(int j = 0; j <= len; j++){
                string curr = sol.substr(0, len-j) + string(n-(len-j), i);
                amount = query(curr);
                int pos = len - j;
                int diff = amount - pos - totalDiff;
                if(diff > 0){
                    add.push_back({pos, diff});
                    initAmount -= diff;
                    totalDiff+=diff;
                    if(initAmount <= 0) break;
                }
            }
            int k = 0;
            sort(add.begin(), add.end());
            for(auto &j : add){
                sol.insert(j.first + k, string(j.second, i));
                k+=j.second;
                // cout << "{" << j.first << " " << j.second << "}" << endl;
            }
            // cout << "| " << sol << " |" << endl;
        }
    }
    assert(sol.size()==n);
    return sol;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from password.cpp:18:
password.cpp: In function 'std::string guess(int, int)':
password.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     assert(sol.size()==n);
      |            ~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Guessed the password with 88 queries.
2 Correct 4 ms 504 KB Guessed the password with 157 queries.

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Guessed the password with 28 queries.
2 Correct 2 ms 336 KB Guessed the password with 103 queries.
3 Correct 1 ms 336 KB Guessed the password with 18 queries.
4 Correct 2 ms 336 KB Guessed the password with 134 queries.

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 708 KB Guessed the password with 3775 queries.
2 Correct 156 ms 468 KB Guessed the password with 9264 queries.
3 Correct 188 ms 708 KB Guessed the password with 9841 queries.
4 Correct 335 ms 472 KB Guessed the password with 18317 queries.

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Guessed the password with 88 queries.
2 Correct 4 ms 504 KB Guessed the password with 157 queries.
3 Correct 2 ms 336 KB Guessed the password with 28 queries.
4 Correct 2 ms 336 KB Guessed the password with 103 queries.
5 Correct 1 ms 336 KB Guessed the password with 18 queries.
6 Correct 2 ms 336 KB Guessed the password with 134 queries.
7 Correct 69 ms 708 KB Guessed the password with 3775 queries.
8 Correct 156 ms 468 KB Guessed the password with 9264 queries.
9 Correct 188 ms 708 KB Guessed the password with 9841 queries.
10 Correct 335 ms 472 KB Guessed the password with 18317 queries.
11 Correct 654 ms 720 KB Guessed the password with 33172 queries.
12 Correct 111 ms 704 KB Guessed the password with 9064 queries.
13 Correct 873 ms 720 KB Guessed the password with 46119 queries.
14 Correct 347 ms 488 KB Guessed the password with 17884 queries.
15 Correct 905 ms 724 KB Guessed the password with 43507 queries.
16 Correct 300 ms 504 KB Guessed the password with 16260 queries.
17 Incorrect 1008 ms 740 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 336 KB Guessed the password with 88 queries.
2 Correct 4 ms 504 KB Guessed the password with 157 queries.
3 Correct 2 ms 336 KB Guessed the password with 28 queries.
4 Correct 2 ms 336 KB Guessed the password with 103 queries.
5 Correct 1 ms 336 KB Guessed the password with 18 queries.
6 Correct 2 ms 336 KB Guessed the password with 134 queries.
7 Correct 69 ms 708 KB Guessed the password with 3775 queries.
8 Correct 156 ms 468 KB Guessed the password with 9264 queries.
9 Correct 188 ms 708 KB Guessed the password with 9841 queries.
10 Correct 335 ms 472 KB Guessed the password with 18317 queries.
11 Correct 654 ms 720 KB Guessed the password with 33172 queries.
12 Correct 111 ms 704 KB Guessed the password with 9064 queries.
13 Correct 873 ms 720 KB Guessed the password with 46119 queries.
14 Correct 347 ms 488 KB Guessed the password with 17884 queries.
15 Correct 905 ms 724 KB Guessed the password with 43507 queries.
16 Correct 300 ms 504 KB Guessed the password with 16260 queries.
17 Incorrect 1008 ms 740 KB Could not guess the password with 50000 queries.
18 Halted 0 ms 0 KB -