oj.uz

Submission #718882

# Submission time Handle Problem Language Result Execution time Memory
718882 2023-04-05T04:47:17 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 40 ms 27916 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];
bool 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 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();
		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;
		}
		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를 돌려 주자.
		// 전이 방향이 반대라서 그래프를 새로 만들어야 한다...
		for(int j=-5000; j<=5000; j++)
			for(int x : X[((0-j)%K+K)%K])
			{
				int nj = (j+x >= 0 ? (j+x)/K : -((-(j+x)+K-1)/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;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26580 KB OK
2 Correct 26 ms 26648 KB OK
3 Correct 25 ms 26636 KB OK
4 Correct 25 ms 26672 KB OK
5 Correct 25 ms 26644 KB OK
6 Correct 26 ms 26604 KB OK
7 Correct 30 ms 26572 KB OK
8 Correct 28 ms 26640 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26580 KB OK
2 Correct 26 ms 26648 KB OK
3 Correct 25 ms 26636 KB OK
4 Correct 25 ms 26672 KB OK
5 Correct 25 ms 26644 KB OK
6 Correct 26 ms 26604 KB OK
7 Correct 30 ms 26572 KB OK
8 Correct 28 ms 26640 KB OK
9 Correct 28 ms 26716 KB OK
10 Correct 26 ms 26836 KB OK
11 Correct 25 ms 26668 KB OK
12 Correct 26 ms 26708 KB OK
13 Correct 40 ms 27916 KB OK
14 Correct 34 ms 27444 KB OK
15 Correct 32 ms 27220 KB OK
16 Incorrect 25 ms 26580 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -