oj.uz

Submission #1102481

# Submission time Handle Problem Language Result Execution time Memory
1102481 2024-10-18T07:54:22 Z vjudge1 Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 1619 ms 1756 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 5e3 + 5;

vector<int> v;
int k, q, d, m, a[NM];
bool ok;
map<int, bool> mp;

int F(int x)
{
    return ((x % k) + k) % k;
}

void dfs(int x)
{
    if (mp[x])
        return;
    if (v.size())
        mp[x] = 1;
    if (v.size() && !x)
    {
        ok = 1;
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i] << " \n"[i == 0];
        return;
    }
    for (int i = 1; i <= d; i++)
        if (F(x) == F(a[i]))
        {
            v.push_back(a[i]);
            dfs((x - a[i]) / k);
            if (ok)
                return;
            v.pop_back();
        }
}

void solve()
{
    cin >> k >> q >> d >> m;
    for (int i = 1; i <= d; i++)
        cin >> a[i];
    while (q--)
    {
        int x;
        cin >> x;
        v.clear();
        mp.clear();
        ok = 0;
        dfs(x);
        if (!ok)
            cout << "IMPOSSIBLE\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB OK
2 Correct 1 ms 336 KB OK
3 Correct 1 ms 336 KB OK
4 Correct 1 ms 504 KB OK
5 Correct 1 ms 336 KB OK
6 Correct 1 ms 336 KB OK
7 Correct 1 ms 336 KB OK
8 Correct 1 ms 336 KB OK
9 Correct 2 ms 336 KB OK
10 Correct 1 ms 336 KB OK
11 Correct 1 ms 336 KB OK
12 Correct 1 ms 336 KB OK
13 Correct 1 ms 508 KB OK
14 Correct 1 ms 336 KB OK
15 Correct 1 ms 336 KB OK
16 Correct 1 ms 508 KB OK
17 Correct 1 ms 336 KB OK
18 Correct 1 ms 336 KB OK
19 Correct 1 ms 336 KB OK
20 Correct 1 ms 336 KB OK
21 Correct 49 ms 1544 KB OK
22 Correct 328 ms 1668 KB OK
23 Correct 1619 ms 1756 KB OK
24 Correct 650 ms 1740 KB OK
25 Correct 1 ms 336 KB OK
26 Correct 1 ms 336 KB OK
27 Correct 1 ms 336 KB OK
28 Correct 1 ms 336 KB OK