oj.uz

답안 #718906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718906 2023-04-05T06:24:52 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 28 ms 26580 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) 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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 26580 KB For n=453315765336943587, representation is not correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 26580 KB For n=453315765336943587, representation is not correct
2 Halted 0 ms 0 KB -