oj.uz

Submission #718874

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

#define INF 1234567890
#define ll long long
#define SZ 80

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 27 ms 26836 KB OK
2 Correct 23 ms 26884 KB OK
3 Correct 24 ms 26884 KB OK
4 Correct 24 ms 26836 KB OK
5 Correct 23 ms 26940 KB OK
6 Correct 24 ms 26844 KB OK
7 Correct 23 ms 26860 KB OK
8 Correct 27 ms 26884 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26836 KB OK
2 Correct 23 ms 26884 KB OK
3 Correct 24 ms 26884 KB OK
4 Correct 24 ms 26836 KB OK
5 Correct 23 ms 26940 KB OK
6 Correct 24 ms 26844 KB OK
7 Correct 23 ms 26860 KB OK
8 Correct 27 ms 26884 KB OK
9 Correct 26 ms 26920 KB OK
10 Correct 25 ms 26924 KB OK
11 Correct 23 ms 26836 KB OK
12 Correct 22 ms 26884 KB OK
13 Correct 22 ms 26928 KB OK
14 Correct 23 ms 26940 KB OK
15 Correct 23 ms 26944 KB OK
16 Incorrect 26 ms 26964 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -