oj.uz

Submission #718875

# Submission time Handle Problem Language Result Execution time Memory
718875 2023-04-05T04:20:49 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 31 ms 31736 KB 
#include<bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long
#define SZ 200

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];

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

	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 i, int j)
{
	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));

		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]);

		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:38:7: warning: unused variable 'ret' [-Wunused-variable]
   38 |  int &ret = dp[i][j+5000];
      |       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31572 KB OK
2 Correct 25 ms 31572 KB OK
3 Correct 25 ms 31572 KB OK
4 Correct 27 ms 31628 KB OK
5 Correct 27 ms 31552 KB OK
6 Correct 26 ms 31628 KB OK
7 Correct 29 ms 31640 KB OK
8 Correct 30 ms 31624 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31572 KB OK
2 Correct 25 ms 31572 KB OK
3 Correct 25 ms 31572 KB OK
4 Correct 27 ms 31628 KB OK
5 Correct 27 ms 31552 KB OK
6 Correct 26 ms 31628 KB OK
7 Correct 29 ms 31640 KB OK
8 Correct 30 ms 31624 KB OK
9 Correct 26 ms 31648 KB OK
10 Correct 29 ms 31736 KB OK
11 Correct 28 ms 31656 KB OK
12 Correct 30 ms 31640 KB OK
13 Correct 27 ms 31656 KB OK
14 Correct 27 ms 31652 KB OK
15 Correct 27 ms 31636 KB OK
16 Incorrect 31 ms 31572 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -