oj.uz

Submission #857234

# Submission time Handle Problem Language Result Execution time Memory
857234 2023-10-05T15:36:20 Z Tudy006 Password (RMI18_password) C++14
80 / 100
 295 ms 1524 KB 
#include <bits/stdc++.h>

using namespace std;

const int SIGMA = 26;

//#define DEBUG 0
//#define MAX_QUERIES 50000
//#define MAX_N 5000
//#define MAX_SIGMA 26
//
//
//static string password;
//static int n, s, numQueries;
//static stringstream msg;
//
//static void end(int success) {
//  cout << (success ? "SUCCESS! " : "ERROR: ") << msg.str() << endl;
//  exit(0);
//}
//
//int query(string q) {
//  if (++numQueries > MAX_QUERIES) {
//    msg << "Could not guess the password with " << MAX_QUERIES << " questions.";
//    end(0);
//  }
//
//  int len = q.size();
//
//  // validation
//  if (len < 1 || len > n) {
//    msg << "Query '" << q << "' should have length between 1 and "
//        << n << " characters.";
//    end(0);
//  }
//
//  for (int i = 0; i < len; i++) {
//    if (q[i] < 'a' || q[i] >= 'a' + s) {
//      msg << "Illegal character '" << q[i] << "' found.";
//      end(0);
//    }
//  }
//
//  // while possible, advance one character in q and find its next
//  // occurrence in password
//  int i = 0, j = 0, plen = password.size();
//  while (i < plen && j < len) {
//    while ((i < plen) && (password[i] != q[j])) {
//      i++;
//    }
//    if (i < plen) { /* found a match */
//      i++;
//      j++;
//    }
//  }
//
//  if (DEBUG) {
//    cout << "Question #" << numQueries << " [" << q << "] answer " << j << endl;
//  }
//  return j;
//}
int query(string str);

int frecv[SIGMA];

void fillCh( string& s, char ch, int n ) {
    s.clear();
    s.resize( n, ch );
}
string insertCh( string s, char ch, int poz ) {
    string aux = s;
    aux.resize( s.size() + 1 );
    for ( int i = aux.size() - 1; i > poz; i -- ) {
        aux[i] = aux[i - 1];
    }
    aux[poz] = ch;
    return aux;
}
int checkQuery( string s, int n ) {
    if ( (int)s.size() > n ) return -1;
    return query( s );
}
string guess(int n, int sig) {
    string s;
    for ( int ch = 0; ch < sig; ch ++ ) {
        fillCh( s, 'a' + ch, n );
        frecv[ch] = query( s );
    }
    s.clear();
    vector <int> order(sig);

    for ( int i = 0; i < sig; i ++ ) {
        order[i] = i;
    }
    sort( order.begin(), order.end(), []( int i, int j ) {
         return frecv[i] < frecv[j];
    } );

    int correct = 0;
    for ( int i = 0; i < sig; i ++ ) {
        int ch = order[i], auxQuery;
        string aux;
        for ( int j = 0; j < (int)s.size(); j ++ ) {

//            cerr << aux << endl;
            while ( ( auxQuery = checkQuery( aux = insertCh( s, 'a' + ch, j ), n ) ) > correct ) {
                s = aux;
                correct = auxQuery;
                j ++;
            }
        }
        while ( ( auxQuery = checkQuery( aux = insertCh( s, 'a' + ch, s.size() ), n ) ) > correct ) {
            s = aux;
            correct = auxQuery;
        }
    }
    return s;
}

//int main() {
//
//  ifstream f("password.in");
//  f >> n >> s >> password;
//  f.close();
//  assert(n && s && !password.empty());
//
//  string answer = guess(n, s);
//  if (DEBUG) {
//    cout << "Your answer: [" << answer << "]\n";
//  }
//
//  if (answer.compare(password)) {
//    msg << "Your answer was [" << answer
//        << "] which does not match the password [" << password << "].";
//    end(0);
//  } else {
//    msg << "You guessed the password with " << numQueries << " queries.";
//    end(1);
//  }
//
//	return 0;
//}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Guessed the password with 148 queries.
2 Correct 1 ms 344 KB Guessed the password with 303 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Guessed the password with 73 queries.
2 Correct 1 ms 344 KB Guessed the password with 103 queries.
3 Correct 1 ms 436 KB Guessed the password with 97 queries.
4 Correct 1 ms 436 KB Guessed the password with 191 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1476 KB Guessed the password with 3159 queries.
2 Correct 46 ms 1028 KB Guessed the password with 9679 queries.
3 Correct 24 ms 1456 KB Guessed the password with 5234 queries.
4 Correct 79 ms 1236 KB Guessed the password with 14047 queries.

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Guessed the password with 148 queries.
2 Correct 1 ms 344 KB Guessed the password with 303 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 344 KB Guessed the password with 103 queries.
5 Correct 1 ms 436 KB Guessed the password with 97 queries.
6 Correct 1 ms 436 KB Guessed the password with 191 queries.
7 Correct 15 ms 1476 KB Guessed the password with 3159 queries.
8 Correct 46 ms 1028 KB Guessed the password with 9679 queries.
9 Correct 24 ms 1456 KB Guessed the password with 5234 queries.
10 Correct 79 ms 1236 KB Guessed the password with 14047 queries.
11 Correct 51 ms 1524 KB Guessed the password with 9438 queries.
12 Correct 52 ms 1200 KB Guessed the password with 9477 queries.
13 Correct 97 ms 1480 KB Guessed the password with 18001 queries.
14 Correct 101 ms 1472 KB Guessed the password with 18376 queries.
15 Correct 82 ms 1212 KB Guessed the password with 14515 queries.
16 Correct 86 ms 1012 KB Guessed the password with 14406 queries.
17 Correct 71 ms 1020 KB Guessed the password with 12275 queries.
18 Correct 70 ms 808 KB Guessed the password with 12344 queries.
19 Correct 62 ms 1012 KB Guessed the password with 11035 queries.
20 Correct 62 ms 984 KB Guessed the password with 11259 queries.
21 Correct 80 ms 804 KB Guessed the password with 15328 queries.
22 Correct 92 ms 1236 KB Guessed the password with 15392 queries.

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Guessed the password with 148 queries.
2 Correct 1 ms 344 KB Guessed the password with 303 queries.
3 Correct 1 ms 344 KB Guessed the password with 73 queries.
4 Correct 1 ms 344 KB Guessed the password with 103 queries.
5 Correct 1 ms 436 KB Guessed the password with 97 queries.
6 Correct 1 ms 436 KB Guessed the password with 191 queries.
7 Correct 15 ms 1476 KB Guessed the password with 3159 queries.
8 Correct 46 ms 1028 KB Guessed the password with 9679 queries.
9 Correct 24 ms 1456 KB Guessed the password with 5234 queries.
10 Correct 79 ms 1236 KB Guessed the password with 14047 queries.
11 Correct 51 ms 1524 KB Guessed the password with 9438 queries.
12 Correct 52 ms 1200 KB Guessed the password with 9477 queries.
13 Correct 97 ms 1480 KB Guessed the password with 18001 queries.
14 Correct 101 ms 1472 KB Guessed the password with 18376 queries.
15 Correct 82 ms 1212 KB Guessed the password with 14515 queries.
16 Correct 86 ms 1012 KB Guessed the password with 14406 queries.
17 Correct 71 ms 1020 KB Guessed the password with 12275 queries.
18 Correct 70 ms 808 KB Guessed the password with 12344 queries.
19 Correct 62 ms 1012 KB Guessed the password with 11035 queries.
20 Correct 62 ms 984 KB Guessed the password with 11259 queries.
21 Correct 80 ms 804 KB Guessed the password with 15328 queries.
22 Correct 92 ms 1236 KB Guessed the password with 15392 queries.
23 Incorrect 295 ms 1508 KB Could not guess the password with 50000 queries.
24 Halted 0 ms 0 KB -