oj.uz

Submission #718907

# Submission time Handle Problem Language Result Execution time Memory
718907 2023-04-05T06:28:29 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
25 / 25
 321 ms 67636 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define INF 1234567890
#define ll long long
#define SZ 60
 
bool rev;
ll N;
int K, Q, D, M;
int A[5001], n[SZ], suf[SZ+1];
vector<int> X[1000000];
vector<pair<int, int> > Y[10001];
int dp[SZ][10001], DP[10001];
pair<int, int> P[10001];
 
int f(int i, int j)
{
	if (i >= SZ) return DP[j+5000];
	if (i > 0 && suf[i]-j == 0) return 1; // 틀린 이유..
 
	int &ret = dp[i][j+5000];
	if (ret != -1) return ret;
	ret = 0;
 
	// j+x = n[i] (mod K)인 x를 사용해야 한다.
	for(int x : X[((n[i]-j)%K+K)%K])
		if (f(i+1, (j+x-n[i])/K))
		{
			ret = 1;
			break;
		}
	return ret;
}
 
void G(int j)
{
	if (j == 0) return;
	auto [nj,x] = P[j+5000];
	G(nj);
	cout << (rev ? -x : x) << " ";
}
 
void g(int i, int j)
{
	if (i >= SZ) { G(j); return; }
	if (i > 0 && suf[i]-j == 0) return; // 틀린 이유..
 
	for(int x : X[((n[i]-j)%K+K)%K])
		if (f(i+1, (j+x-n[i])/K))
		{
			g(i+1, (j+x-n[i])/K);
			cout << (rev ? -x : x) << " \n"[i==0];
			return;
		}
}
 
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;
		for(int i=0; i<1000000; i++)
			X[i].clear();
		for(int i=0; i<10001; i++)
			Y[i].clear();
		memset(dp, -1, sizeof(dp));
		memset(DP, 0, sizeof(DP));
 
		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<SZ; i++)
		{
			n[i] = N % K;
			N /= K;
		}

		// 틀린 이유: n의 자릿수는 10자리인데 x는 정확히 8번을 사용해야 답을 구할 수 있는 경우가 존재한다.
		// n에서 아직 보지 않은 자리들의 합이 올림값 j와 상쇄될 경우, 더 이상 진행하지 않고 가능하다고 판정해야 한다.
		suf[SZ] = 0;
		for(int i=SZ-1; i>=0; i--)
			suf[i] = min((ll)INF, (ll)suf[i+1] * K + n[i]);
 
		for(int i=1; i<=D; i++)
			X[(A[i]%K+K)%K].push_back(A[i]);
 
		// 길이가 매우 길 수 있나? i >= 60에서는 BFS를 돌려 주자.
		// 전이 방향이 반대라서 그래프를 새로 만들어야 한다...
		for(int j=-5000; j<=5000; j++)
			for(int x : X[((0-j)%K+K)%K])
			{
				int nj = (j+x)/K;
				Y[nj+5000].push_back({j, x}); // j에서 x를 사용하면 nj로 갈 수 있다.
			}
 
		queue<int> q;
		q.push(0), DP[0+5000] = 1;
		while(!q.empty())
		{
			int j = q.front(); q.pop();
			for(auto [pj,x] : Y[j+5000]) // j로 올 수 있는 애들
			{
				if (DP[pj+5000]) continue;
				q.push(pj), DP[pj+5000] = 1, P[pj+5000] = {j, x};
			}
		}
 
		if (!f(0, 0)) cout << "IMPOSSIBLE\n";
		else g(0, 0); // 역추적
 
		if (rev)
			for(int i=1; i<=D; i++)
				A[i] = -A[i];
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26580 KB OK
2 Correct 25 ms 26568 KB OK
3 Correct 26 ms 26540 KB OK
4 Correct 24 ms 26672 KB OK
5 Correct 24 ms 26644 KB OK
6 Correct 24 ms 26620 KB OK
7 Correct 23 ms 26528 KB OK
8 Correct 25 ms 26748 KB OK

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 26580 KB OK
2 Correct 25 ms 26568 KB OK
3 Correct 26 ms 26540 KB OK
4 Correct 24 ms 26672 KB OK
5 Correct 24 ms 26644 KB OK
6 Correct 24 ms 26620 KB OK
7 Correct 23 ms 26528 KB OK
8 Correct 25 ms 26748 KB OK
9 Correct 26 ms 26764 KB OK
10 Correct 25 ms 26736 KB OK
11 Correct 25 ms 26708 KB OK
12 Correct 26 ms 26708 KB OK
13 Correct 35 ms 27888 KB OK
14 Correct 31 ms 27416 KB OK
15 Correct 29 ms 27220 KB OK
16 Correct 25 ms 26632 KB OK
17 Correct 23 ms 26484 KB OK
18 Correct 169 ms 47088 KB OK
19 Correct 310 ms 67636 KB OK
20 Correct 22 ms 26452 KB OK
21 Correct 55 ms 29240 KB OK
22 Correct 255 ms 47624 KB OK
23 Correct 321 ms 46964 KB OK
24 Correct 284 ms 47668 KB OK
25 Correct 178 ms 47652 KB OK
26 Correct 188 ms 47572 KB OK
27 Correct 20 ms 26632 KB OK
28 Correct 15 ms 26388 KB OK