結果
問題 | No.2768 Password Crack |
ユーザー |
![]() |
提出日時 | 2024-05-31 21:57:14 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 7,353 bytes |
コンパイル時間 | 3,888 ms |
コンパイル使用メモリ | 235,240 KB |
実行使用メモリ | 25,476 KB |
平均クエリ数 | 981.87 |
最終ジャッジ日時 | 2024-12-20 23:19:33 |
合計ジャッジ時間 | 6,631 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:249:25: warning: 'res' may be used uninitialized [-Wmaybe-uninitialized] 249 | ans += char('a' + res); | ~~~~^~~~~ main.cpp:234:13: note: 'res' was declared here 234 | int res; | ^~~
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;namespace random_generator {mt19937_64 generate;void init() {random_device seed_gen;generate = mt19937_64(seed_gen());}template <typename T>T random_int(T x) {assert(x > 0);return generate() % x;}template <typename T>T random_int(T x, T y) {assert(x < y);return x + generate() % (y - x);}} // namespace random_generatornamespace random_generator {template <typename T>T get_elememt(vector<T>& a) {const int n = a.size();int idx = random_int(0, n);swap(a[n - 1], a[idx]);int ret = a.back();a.pop_back();return ret;}template <typename T>vector<T> random_array_int(int n, T lo, T hi, bool no_dup = false) {vector<T> ret(n);if (!no_dup) {for (int i = 0; i < n; i++) {ret[i] = random_int(lo, hi);}} else {set<T> st;for (int i = 0; i < n; i++) {int r = random_int(lo, hi);while (st.count(r)) {r = random_int(lo, hi);}ret[i] = r;st.insert(r);}}return ret;}string random_alphabet(int n, bool lower = true) {string ret;for (int i = 0; i < n; i++) {int idx = random_int(26);ret.push_back(char((lower ? 'a' : 'A') + idx));}return ret;}string random_string(int n, string s) {string ret;int m = s.size();for (int i = 0; i < n; i++) {int idx = random_int(m);ret.push_back(s[idx]);}return ret;}template <typename T>vector<vector<T>> random_array_2D(int h, int w, T lo, T hi) {vector<vector<T>> ret(h, vector<T>(w));for (int i = 0; i < h; i++) {ret[i] = random_array_int(w, lo, hi);}return ret;}vector<string> random_alphabet_2D(int h, int w, bool lower = true) {vector<string> ret(h);for (int i = 0; i < h; i++) {ret[i] = random_alphabet(w, lower);}return ret;}vector<pair<int, int>> random_tree(int n) {vector<int> a = random_array_int<int>(n - 2, 1, n + 1);vector<int> d(n + 1);for (int i = 0; i < n - 2; i++) {d[a[i]]++;}for (int i = 1; i <= n; i++) {d[i]++;}vector<pair<int, int>> ret;set<int> pq;for (int i = 1; i <= n; i++) {if (d[i] == 1) {pq.insert(i);}}for (int i = 0; i < n - 2; i++) {int v = (*pq.begin());pq.erase(v);ret.push_back(make_pair(v, a[i]));d[v]--;d[a[i]]--;if (d[a[i]] == 1) {pq.insert(a[i]);} else if (d[a[i]] == 0) {pq.erase(a[i]);}}for (int i = 1; i <= n; i++) {if (d[i] == 1) {for (int j = i + 1; j <= n; j++) {if (d[j] == 1) {ret.push_back(make_pair(i, j));break;}}break;}}return ret;}vector<pair<int, int>> random_bintree(int n) {vector<pair<int, int>> ret;vector<ll> roots = {random_int(1, n + 1)};vector<ll> leaves;for (int i = 1; i <= n; i++) {if (i != roots.back()) {leaves.push_back(i);}}while (!leaves.empty()) {int root = get_elememt(roots);int leaf = get_elememt(leaves);ret.push_back(make_pair(root, leaf));roots.push_back(leaf);if (!leaves.empty()) {int leaf = get_elememt(leaves);ret.push_back(make_pair(root, leaf));roots.push_back(leaf);}}return ret;}vector<pair<int, int>> random_undigraph(int n, int m, bool connected = true) {vector<pair<int, int>> edges;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {edges.push_back(make_pair(i + 1, j + 1));}}int ed = edges.size();if (!connected) {vector<pair<int, int>> ret;vector<int> idxs = random_array_int<int>(m, 0, ed, true);for (int idx : idxs) {ret.push_back(edges[idx]);}return ret;} else {vector<pair<int, int>> ret;while (true) {ret.clear();vector<int> idxs = random_array_int<int>(m, 0, ed, true);vector<int> parent(n);vector<vector<int>> sets(n);for (int i = 0; i < n; i++) {parent[i] = i;sets[i].push_back(i);}for (int idx : idxs) {ret.push_back(edges[idx]);auto [a, b] = edges[idx];a--;b--;if (parent[a] != parent[b]) {if (sets[parent[a]].size() < sets[parent[b]].size()) {swap(a, b);}for (int x : sets[parent[b]]) {parent[x] = parent[a];sets[parent[a]].push_back(x);}sets[parent[b]].clear();}}bool ok = true;for (int i = 0; i < n; i++) {if (parent[i] != parent[0]) {ok = false;break;}}if (ok) {return ret;}}}}}; // namespace random_generatorstruct setup_random {setup_random() {random_generator::init();}} setup_random;int main() {int N;cin >> N;auto Ask = [&](string T) {cout << "? " << T << endl;int ret;cin >> ret;return ret;};auto Say = [&](string T) {cout << "! " << T << endl;};string ans;for (int i = 0; i < N; i++) {auto P = random_generator::random_array_int(26, 0, 26, true);string T(N, 'a');map<int, vector<int>> cnt;int res;for (int j = 0; j < 26; j++) {T[i] = char('a' + P[j]);cnt[Ask(T)].push_back(P[j]);if (cnt.size() == 2) {auto [a, b] = *cnt.begin();auto [c, d] = *next(cnt.begin());if (b.size() == d.size()) {continue;} else {res = (b.size() > d.size() ? d : b)[0];break;}}}ans += char('a' + res);}Say(ans);}