#include<bits/stdc++.h>
using namespace std;
#define INF 1234567890
#define ll long long
bool rev;
ll N;
int K, Q, D, M;
int A[5001], n[60], suf[61]; // suf[i] : [i, ...]번째 자리가 전부 0인가?
vector<int> com;
int ord[1000000];
bitset<10001> X[5001];
bitset<10001> dp[61];
bitset<10001> ep;
int p[61][10001]; // 사용한 x값 (역추적용)
void f(int i, int j) // backtrack
{
if (i == 60) return;
if (i > 0 && suf[i] && j == 5000) return;
int x = p[i][j];
j -= 5000;
f(i+1, (j+x-n[i] >= 0 ? (j+x-n[i])/K+5000 : -((-(j+x-n[i])+K-1)/K)+5000));
cout << (rev ? -x : x);
if (i) cout << " "; // 줄 끝에 공백을 출력하면 틀린다;;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin >> K >> Q >> D >> M;
for(int i=1; i<=D; i++)
cin >> A[i];
while(Q--)
{
// clear
rev = false;
com.clear();
memset(ord, -1, sizeof(ord));
for(int i=0; i<5001; i++)
X[i].reset();
for(int i=0; i<61; i++)
dp[i].reset();
cin >> N;
if (N < 0)
{
rev = true;
N = -N;
for(int i=1; i<=D; i++)
A[i] = -A[i];
}
for(int i=0; i<60; i++)
{
n[i] = N % K;
N /= K;
}
suf[60] = 1;
for(int i=59; i>=0; i--)
suf[i] = (suf[i+1] & (n[i] == 0));
for(int i=1; i<=D; i++)
com.push_back((A[i]%K+K)%K);
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
for(int i=0; i<com.size(); i++)
ord[com[i]] = i;
for(int i=1; i<=D; i++)
X[ord[(A[i]%K+K)%K]][A[i]+5000] = 1;
// dp[i][j] : i번째 자리에 j-5000만큼 올림되었을 때, 가능한가?
// ep[j] : i번째 자리를 j-5000로 결정했다면 올림되는 값을 x라 했을 때, dp[i+1][x]값
dp[60][5000] = 1;
for(int i=59; i>=0; i--)
{
for(int j=0; j<=10000; j++)
ep[j] = (j-5000 >= 0 ? dp[i+1][(j-5000)/K+5000] : dp[i+1][-((-(j-5000)+K-1)/K)+5000]);
for(int j=-2500; j<=2500; j++)
{
if (i > 0 && suf[i] && j == 0) // base case, N=0일때 x를 하나 이상 사용해야 함에 유의
{
dp[i][j+5000] = 1;
continue;
}
// x = n[i]-j (mod K)를 만족하는 x를 사용
int pos = ord[((n[i]-j)%K+K)%K];
if (pos == -1) continue;
// 이번 자리에는 j+x를 놓을 것이다. (j+x-n[i])만큼이 올림된다.
int idx = (ep & ((j-n[i]) >= 0 ? (X[pos] << (j-n[i])) : (X[pos] >> -(j-n[i]))))._Find_first();
dp[i][j+5000] = (idx < 10001);
if (dp[i][j+5000]) p[i][j+5000] = (idx - (j-n[i]) - 5000);
}
}
if (!dp[0][5000]) cout << "IMPOSSIBLE\n";
else { f(0, 5000); cout << "\n"; }
if (rev) // 틀린 이유..
for(int i=1; i<=D; i++)
A[i] = -A[i];
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0; i<com.size(); i++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
350 ms |
11804 KB |
OK |
| 2 |
Correct |
464 ms |
11724 KB |
OK |
| 3 |
Correct |
514 ms |
11844 KB |
OK |
| 4 |
Correct |
543 ms |
11852 KB |
OK |
| 5 |
Correct |
552 ms |
11760 KB |
OK |
| 6 |
Correct |
571 ms |
11944 KB |
OK |
| 7 |
Correct |
673 ms |
11724 KB |
OK |
| 8 |
Correct |
677 ms |
11904 KB |
OK |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
350 ms |
11804 KB |
OK |
| 2 |
Correct |
464 ms |
11724 KB |
OK |
| 3 |
Correct |
514 ms |
11844 KB |
OK |
| 4 |
Correct |
543 ms |
11852 KB |
OK |
| 5 |
Correct |
552 ms |
11760 KB |
OK |
| 6 |
Correct |
571 ms |
11944 KB |
OK |
| 7 |
Correct |
673 ms |
11724 KB |
OK |
| 8 |
Correct |
677 ms |
11904 KB |
OK |
| 9 |
Correct |
649 ms |
11836 KB |
OK |
| 10 |
Correct |
452 ms |
11948 KB |
OK |
| 11 |
Correct |
651 ms |
11900 KB |
OK |
| 12 |
Correct |
649 ms |
11852 KB |
OK |
| 13 |
Correct |
640 ms |
11860 KB |
OK |
| 14 |
Correct |
641 ms |
11836 KB |
OK |
| 15 |
Correct |
638 ms |
11836 KB |
OK |
| 16 |
Incorrect |
333 ms |
11360 KB |
Query 1: Jury has an answer but participant does not |
| 17 |
Halted |
0 ms |
0 KB |
- |
