Submission #1102517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102517		vjudge1	Weird Numeral System (CCO21_day1problem2)	C++17	25 / 25	1083 ms	25244 KiB

Main

// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define no cout << "NO\n"
#define yes cout << "YES\n"
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) a * b / gcd(a, b)
#define all(v) v.begin(),v.end()
#define ret(a) return void(cout << a << "\n")
#define coutf(x) cout << fixed << setprecision(x) 
#define inter(a) cout << a << "\n"; fflush(stdout)
#define shuf(v) shuffle(all(v), rnd);
#define sortuni(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define ar1d(a) for (int i = 1; i <= n; ++i) cin >> a[i];
#define ar2d(a) for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) cin >> a[i][j];
#define graph(n, m) for (int i = 1; i <= m; ++i){int u, v; cin >> u >> v;g[u].push_back(v); g[v].push_back(u);};
#define graphd(n, m) for (int i = 1; i <= m; ++i){int u, v; cin >> u >> v;g[u].push_back(v);};
#define graphw(n, m) for (int i = 1; i <= m; ++i){int u, v, w; cin >> u >> v >> w;g[u].push_back({v, w}); g[v].push_back({u, w});};
#define graphdw(n, m) for (int i = 1; i <= m; ++i){int u, v, w; cin >> u >> v >> w;g[u].push_back({v, w});};
#define graph1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i]; cin >> u[i] >> v[i];g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]);}
#define graphd1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i]; cin >> u[i] >> v[i];g[u[i]].push_back(v[i]);}
#define graphw1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i], w[i]; cin >> u[i] >> v[i] >> w[i];g[u[i]].push_back({v[i], w[i]}); g[v[i]].push_back({u[i], w[i]});}
#define graphdw1(n, m) for (int i = 1; i <= m; ++i){int u[i], v[i], w[i]; cin >> u[i] >> v[i] >> w[i];g[u[i]].push_back({v[i], w[i]});}
#define trees(n) for (int i = 2; i <= n; ++i){int p; cin >> p; g[p].push_back(i);}
#define trees1(n) for (int i = 2; i <= n; ++i){int p[i]; cin >> p[i]; g[p[i]].push_back(i);}
 
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
 
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
void _max(int &a, int b){a = max(a, b);}
void _min(int &a, int b){a = min(a, b);}
bool is_square(ll n){ll k = sqrt(n); return k * k == n;}
bool is_prime(ll n){if (n <= 3) return n > 1; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i <= sqrt(n); i += 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}
ll rand(ll l, ll r){ll d = r - l + 1; return rnd() % d + l;}
ll bin_pow(ll a, ll b, ll MOD){ll ans = 1; if (a >= MOD) a %= MOD; while (b){if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
ll bin_mul(ll a, ll b, ll MOD){ll ans = 0; if (a >= MOD) a %= MOD; while (b){if (b & 1) ans = (ans + a) % MOD; a = (a + a) % MOD; b /= 2;} return ans;}
// build(n, mod)
struct math{int N, MOD; vector <int> gt, rl; void build(int n, int mod){N = n; MOD = mod; gt.resize(N + 5); rl.resize(N + 5); gt[0] = rl[0] = 1; for (int i = 1; i <= N; ++i){gt[i] = 1LL * gt[i - 1] * i % MOD; rl[i] = bin_pow(gt[i], MOD - 2, MOD);}} int C(int a, int b){return 1LL * gt[b] * rl[a] % MOD * rl[b - a] % MOD;}};
// build(mod)
struct fibonacci{int MOD; map <ll,int> fibo; void build(int mod){MOD = mod; fibo[1] = fibo[2] = 1;} int fb(ll n){if (fibo.count(n)) return fibo[n]; if (n & 1) return fibo[n] = (1LL * fb(n / 2) * fb(n / 2) + 1LL * fb(n / 2 + 1) * fb(n / 2 + 1)) % MOD; return fibo[n] = (1LL * 2 * fb(n / 2 - 1) * fb(n / 2) + 1LL * fb(n / 2) * fb(n / 2)) % MOD;}};
 
const int D = 5e3, K = 1e6;
vector <int> ans, md[K + 5];
int k, q, d, m, a[D + 5];
map <int,bool> mp;
 
bool Check(int n)
{
    if (mp.count(n)) return false;
    mp[n] = true;
    int p = n % k;
    if (p < 0) p += k;
    for (int x : md[p])
    {
        if (n == x)
        {
            ans.push_back(x);
            return true;
        }
        else if (Check((n - x) / k))
        {
            ans.push_back(x);
            return true;
        }
    }
    return false;
}
 
void Solve()
{
    cin >> k >> q >> d >> m;
    for (int i = 1; i <= d; ++i)
    {
        cin >> a[i];
        int p = a[i] % k;
        if (p < 0) p += k;
        md[p].push_back(a[i]);
    }
    while (q--)
    {
        int n;
        cin >> n;
        mp.clear();
        ans.clear();
        if (Check(n))
        {
            for (int i = 0; i < ans.size(); ++i)
            {
                cout << ans[i];
                if (i < ans.size() - 1) cout << ' ';
            }
        }
        else cout << "IMPOSSIBLE";
        if (q) cout << "\n";
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("file.inp", "r"))
    {
        freopen ("file.inp", "r", stdin);
        freopen ("file.out", "w", stdout);
    }
    int TEST = 1;
    // cin >> TEST;
    while (TEST--) Solve();
    cerr << "\nTIME: " << 1000 * clock() / CLOCKS_PER_SEC << "ms.";
}

Compilation message (stderr)

Main.cpp: In function 'void Solve()':
Main.cpp:93:31: 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]
   93 |             for (int i = 0; i < ans.size(); ++i)
      |                             ~~^~~~~~~~~~~~
Main.cpp:96: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]
   96 |                 if (i < ans.size() - 1) cout << ' ';
      |                     ~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:111:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen ("file.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:112:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen ("file.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17