oj.uz

Submission #433853

# Submission time Handle Problem Language Result Execution time Memory
433853 2021-06-20T11:30:07 Z HediChehaidar Password (RMI18_password) C++17
10 / 100
 6 ms 200 KB 
/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

/*string str;
int query(string s){
  //  cout << s << " ";
    int cur = 0 , ans = 0;
    for(auto c : s){
      //  cout << c << " ";
        bool ok = false;
        for(int i = cur ; i < str.length() ; i++){
           // cout << str[i]  << " ";
            if(c == str[i]){
                ans++;
                cur = i + 1;
                ok = true;
                break;
            }
        }
        if(ok) continue;
        break;
    }
   // cout << s << " " << ans << "\n";
   // cout << endl;
    return ans;
}*/
int query(string s);
bool least[27][27];
vector<char> v;
bool comp(char a , char b){
    return least[a - 'a'][b - 'a'];
}
string guess(int n , int s){
    for(int i = 0 ; i < s ; i++){
        string res = "";
        res += ('a' + i);
        if(query(res)) v.pb('a' + i);
    }
    if(n == 1){
        string res = ""; res += v[0]; return res;
    }
    for(int i = 0 ; i < v.size() ; i++){
        for(int j = i + 1 ; j < v.size() ; j++ ){
            string res = ""; res += v[i]; res += v[j];
            int a = v[i] - 'a', b = v[j] - 'a';
            if(query(res) == 2){
                least[a][b] = true;
            }
            else least[b][a] = true;
        }
    }
    sort(all(v) , comp);
    string res = "";
    for(auto c : v) res += c;
    return res;
}

/*int main(){
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n  ; cin>>n;
    cin>>str;
    cout << guess(str.length() , n);
    for(int i = 0 ; i < 26 ; i++){
        for(int j = 0 ; j < 26 ; j++)
            cout << least[i][j];
        cout << "\n";
    }
    return 0;
}*/

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0 ; i < v.size() ; i++){
      |                     ~~^~~~~~~~~~
password.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = i + 1 ; j < v.size() ; j++ ){
      |                             ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 6 ms 200 KB Guessed the password with 277 queries.

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 200 KB Returned early from guess() after 4 queries.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Returned early from guess() after 79 queries.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 6 ms 200 KB Guessed the password with 277 queries.
3 Incorrect 1 ms 200 KB Returned early from guess() after 4 queries.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Guessed the password with 121 queries.
2 Correct 6 ms 200 KB Guessed the password with 277 queries.
3 Incorrect 1 ms 200 KB Returned early from guess() after 4 queries.
4 Halted 0 ms 0 KB -