oj.uz

Submission #1102399

# Submission time Handle Problem Language Result Execution time Memory
1102399 2024-10-18T04:02:07 Z vjudge1 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1059 ms 25200 KB 
#include <iostream>
#include <queue>
#include <map>
using namespace std;
#define int long long
map<int, int> m;
vector<int> g[1000005], res;
int k;
bool trya(int x) {
    if (m.count(x)) return false;
    int h = (x % k + k) % k;
    m[x] = 0;
    for (int i = 0; i < g[h].size(); i++) {
      	int w = g[h][i];
        if (x == w) {
            res.push_back(w);
            return true;
        }
        if ((x - w) / k != x && trya((x - w) / k)) {
            res.push_back(w);
            return true;
        }
    }
    return false;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int q, d, ma;
    cin >> k >> q >> d >> ma;
    for (int i = 1; i <= d; i++) {
        int x, y;
        cin >> x;
        y = (x % k + k) % k;
        g[y].push_back(x);
    }
    for (int jj = 0; jj < q; jj++) {
        int x, y;
        cin >> x;
        m.clear();
        res.clear();
        y = trya(x);
        if (y == 0) {
            cout << "IMPOSSIBLE" << '\n';
            continue;
        }
        for (int i = 0; i < res.size(); i++) cout << res[i] << " \n"[i+1==(int)res.size()];
    }
}

Compilation message

Main.cpp: In function 'bool trya(long long int)':
Main.cpp:13:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < g[h].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:47:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < res.size(); i++) cout << res[i] << " \n"[i+1==(int)res.size()];
      |                         ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23888 KB OK
2 Correct 5 ms 23888 KB OK
3 Correct 6 ms 23888 KB OK
4 Correct 5 ms 23888 KB OK
5 Correct 5 ms 23932 KB OK
6 Correct 5 ms 23888 KB OK
7 Correct 7 ms 23888 KB OK
8 Correct 5 ms 23888 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23888 KB OK
2 Correct 5 ms 23888 KB OK
3 Correct 6 ms 23888 KB OK
4 Correct 5 ms 23888 KB OK
5 Correct 5 ms 23932 KB OK
6 Correct 5 ms 23888 KB OK
7 Correct 7 ms 23888 KB OK
8 Correct 5 ms 23888 KB OK
9 Correct 6 ms 23888 KB OK
10 Correct 5 ms 23888 KB OK
11 Correct 5 ms 23888 KB OK
12 Correct 5 ms 23888 KB OK
13 Correct 5 ms 23888 KB OK
14 Correct 6 ms 23888 KB OK
15 Correct 5 ms 23888 KB OK
16 Correct 5 ms 24140 KB OK
17 Correct 5 ms 23888 KB OK
18 Correct 5 ms 23888 KB OK
19 Correct 5 ms 23888 KB OK
20 Correct 6 ms 23888 KB OK
21 Correct 41 ms 25160 KB OK
22 Correct 228 ms 25104 KB OK
23 Correct 1059 ms 25200 KB OK
24 Correct 444 ms 25044 KB OK
25 Correct 6 ms 23888 KB OK
26 Correct 5 ms 23888 KB OK
27 Correct 5 ms 23888 KB OK
28 Correct 5 ms 23888 KB OK