oj.uz

Submission #755968

# Submission time Handle Problem Language Result Execution time Memory
755968 2023-06-10T18:48:59 Z vjudge1 Password (RMI18_password) C++17
50 / 100
 821 ms 428 KB 
#include <bits/stdc++.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

#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) {  
      i++;
      j++;
    }
  }

  if (DEBUG) {
    cout << "Question #" << numQueries << " [" << q << "] answer " << j << endl;
  }
  return j;
}*/
int query(string q);
string guess(int n, int s){
    string res="";
    int sum=0;
    int cur=0;
    int tab[s];
    for (int i = 0; i < s; ++i)
    {
        string t="";
        for (int j = 0; j < n; ++j)
        {
            char x=char(i+'a');
            t.push_back(x);
        }
        tab[i]=query(t);
    }
    int check[s];
    memset(check,0,sizeof check);
    int lst=-1;
    while(cur<n)
    {
        bool test=false;
        for (int i = 0; i < s; ++i)
        {
            if (check[i]==tab[i]) continue;
            if (lst!=-1&&i<lst) continue;
            string t="";
            char x=char(i+'a');
            for (int i = 0; i < cur; ++i)
            {
                t.push_back(res[i]);
            }t.push_back(x);
            for (int i = cur; i < res.size(); ++i)
            {
                t.push_back(res[i]);
            }
            if (t.size()>n) break;
            if (query(t)>sum){
                sum++;
                check[i]++;
                test=true;
                res="";
                lst=i;
                for (int i = 0; i < t.size(); ++i)
                {
                    res.push_back(t[i]);
                }
                break;
            }
        }
        if(!test||lst==s-1){
            cur++;
            lst=-1;
        }
    }
    //cout<< sum<<endl;
    return res;
}

/*int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
  //ifstream f("password.in");
  cin >> 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;
}*/

Compilation message

password.cpp: In function 'std::string guess(int, int)':
password.cpp:97:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for (int i = cur; i < res.size(); ++i)
      |                               ~~^~~~~~~~~~~~
password.cpp:101:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |             if (t.size()>n) break;
      |                 ~~~~~~~~^~
password.cpp:108:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 for (int i = 0; i < t.size(); ++i)
      |                                 ~~^~~~~~~~~~
password.cpp: At global scope:
password.cpp:20:13: warning: 'void end(int)' defined but not used [-Wunused-function]
   20 | static void end(int success) {
      |             ^~~
password.cpp:17:18: warning: 'numQueries' defined but not used [-Wunused-variable]
   17 | static int n, s, numQueries;
      |                  ^~~~~~~~~~
password.cpp:17:15: warning: 's' defined but not used [-Wunused-variable]
   17 | static int n, s, numQueries;
      |               ^
password.cpp:17:12: warning: 'n' defined but not used [-Wunused-variable]
   17 | static int n, s, numQueries;
      |            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 118 queries.
2 Correct 3 ms 208 KB Guessed the password with 262 queries.

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Guessed the password with 72 queries.
2 Correct 2 ms 208 KB Guessed the password with 185 queries.
3 Correct 2 ms 208 KB Guessed the password with 181 queries.
4 Correct 4 ms 208 KB Guessed the password with 359 queries.

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 428 KB Guessed the password with 10003 queries.
2 Correct 208 ms 304 KB Guessed the password with 18426 queries.
3 Correct 267 ms 288 KB Guessed the password with 23271 queries.
4 Correct 623 ms 320 KB Guessed the password with 38297 queries.

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 118 queries.
2 Correct 3 ms 208 KB Guessed the password with 262 queries.
3 Correct 1 ms 208 KB Guessed the password with 72 queries.
4 Correct 2 ms 208 KB Guessed the password with 185 queries.
5 Correct 2 ms 208 KB Guessed the password with 181 queries.
6 Correct 4 ms 208 KB Guessed the password with 359 queries.
7 Correct 132 ms 428 KB Guessed the password with 10003 queries.
8 Correct 208 ms 304 KB Guessed the password with 18426 queries.
9 Correct 267 ms 288 KB Guessed the password with 23271 queries.
10 Correct 623 ms 320 KB Guessed the password with 38297 queries.
11 Incorrect 821 ms 424 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Guessed the password with 118 queries.
2 Correct 3 ms 208 KB Guessed the password with 262 queries.
3 Correct 1 ms 208 KB Guessed the password with 72 queries.
4 Correct 2 ms 208 KB Guessed the password with 185 queries.
5 Correct 2 ms 208 KB Guessed the password with 181 queries.
6 Correct 4 ms 208 KB Guessed the password with 359 queries.
7 Correct 132 ms 428 KB Guessed the password with 10003 queries.
8 Correct 208 ms 304 KB Guessed the password with 18426 queries.
9 Correct 267 ms 288 KB Guessed the password with 23271 queries.
10 Correct 623 ms 320 KB Guessed the password with 38297 queries.
11 Incorrect 821 ms 424 KB Could not guess the password with 50000 queries.
12 Halted 0 ms 0 KB -