Submission #857234

#	Time	Username	Problem	Language	Result	Execution time	Memory
857234		Tudy006	Password (RMI18_password)	C++14	80 / 100	295 ms	1524 KiB

password

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20