Submission #718880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
718880	2023-04-05T04:34:05 Z	edenooo	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	26 ms	26164 KB

Main

#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];
bool suf[SZ+1];
vector<int> X[1000000];
int dp[SZ][10001], DP[10001];
pair<int, int> P[10001];

int f(int i, int j)
{
	if (i >= SZ) return DP[j];
	if (i > 0 && suf[i] && j == 0) return true;

	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] >= 0 ? (j+x-n[i])/K : -((-(j+x-n[i])+K-1)/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;
	int &ret = dp[i][j+5000];

	for(int x : X[((n[i]-j)%K+K)%K])
		if (f(i+1, (j+x-n[i] >= 0 ? (j+x-n[i])/K : -((-(j+x-n[i])+K-1)/K))))
		{
			g(i+1, (j+x-n[i] >= 0 ? (j+x-n[i])/K : -((-(j+x-n[i])+K-1)/K)));
			cout << (rev ? -x : x) << " \n"[i==0];
			break;
		}
}

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();
		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;
		}
		suf[SZ] = true;
		for(int i=SZ-1; i>=0; i--)
			suf[i] = suf[i+1] && (n[i] == 0);

		for(int i=1; i<=D; i++)
			X[(A[i]%K+K)%K].push_back(A[i]);

		// 길이가 매우 길 수 있나? i >= 60에서는 BFS를 돌려 주자.
		queue<int> q;
		q.push(0), DP[0+5000] = 1;
		while(!q.empty())
		{
			int j = q.front(); q.pop();
			for(int x : X[((0-j)%K+K)%K])
			{
				int nj = (j+x >= 0 ? (j+x)/K : -((-(j+x)+K-1)/K));
				if (DP[nj+5000]) continue;
				q.push(nj), DP[nj+5000] = 1, P[nj+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;
}

Compilation message

Main.cpp: In function 'void g(int, int)':
Main.cpp:48:7: warning: unused variable 'ret' [-Wunused-variable]
   48 |  int &ret = dp[i][j+5000];
      |       ^~~

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	26164 KB	Query 2: Jury has an answer but participant does not
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	26164 KB	Query 2: Jury has an answer but participant does not
2	Halted	0 ms	0 KB	-