Submission #718793

#	Time	Username	Problem	Language	Result	Execution time	Memory
718793		edenooo	Weird Numeral System (CCO21_day1problem2)	C++17	8 / 25	1012 ms	12460 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long

bool rev;
ll N;
int K, Q, D, M;
int A[5001], n[80], suf[81]; // suf[i] : [i, ...]번째 자리가 전부 0인가?
vector<int> com;
int ord[1000000];
bitset<10001> X[5001];
bitset<10001> dp[81];
bitset<10001> ep;
int p[81][10001]; // 사용한 x값 (역추적용)

void f(int i, int j) // backtrack
{
	if (i == 80) return;
	if (i > 0 && suf[i] && j == 5000) return;

	int x = p[i][j];

	j -= 5000;
	f(i+1, (j+x >= 0 ? (j+x)/K+5000 : -((-(j+x)+K-1)/K)+5000));

	cout << (rev ? -x : x);
	if (i) cout << " "; // 줄 끝에 공백을 출력하면 틀린다;;
}

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;
		com.clear();
		memset(ord, -1, sizeof(ord));
		for(int i=0; i<5001; i++)
			X[i].reset();
		for(int i=0; i<81; i++)
			dp[i].reset();

		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<80; i++)
		{
			n[i] = N % K;
			N /= K;
		}
		suf[80] = 1;
		for(int i=79; i>=0; i--)
			suf[i] = (suf[i+1] & (n[i] == 0));

		for(int i=1; i<=D; i++)
			com.push_back((A[i]%K+K)%K);
		sort(com.begin(), com.end());
		com.erase(unique(com.begin(), com.end()), com.end());
		for(int i=0; i<com.size(); i++)
			ord[com[i]] = i;
		for(int i=1; i<=D; i++)
			X[ord[(A[i]%K+K)%K]][A[i]+5000] = 1;

		// dp[i][j] : i번째 자리에 j-5000만큼 올림되었을 때, 가능한가?
		// ep[j] : i번째 자리를 j-5000로 결정했다면 올림되는 값을 x라 했을 때, dp[i+1][x]값
		dp[80][5000] = 1;
		for(int i=79; i>=0; i--)
		{
			for(int j=0; j<=10000; j++)
				ep[j] = (j-5000 >= 0 ? dp[i+1][(j-5000)/K+5000] : dp[i+1][-((-(j-5000)+K-1)/K)+5000]);

			for(int j=-2500; j<=2500; j++)
			{
				if (i > 0 && suf[i] && j == 0) // base case, N=0일때 x를 하나 이상 사용해야 함에 유의
				{
					dp[i][j+5000] = 1;
					continue;
				}

				// x = n[i]-j (mod K)를 만족하는 x를 사용
				int pos = ord[((n[i]-j)%K+K)%K];
				if (pos == -1) continue;

				// 이번 자리에는 j+x를 놓을 것이다.
				int idx = (ep & (j >= 0 ? (X[pos] << j) : (X[pos] >> -j)))._Find_first();
				dp[i][j+5000] = (idx < 10001);
				if (dp[i][j+5000]) p[i][j+5000] = (idx - j - 5000);
			}
		}

		if (!dp[0][5000]) cout << "IMPOSSIBLE\n";
		else { f(0, 5000); cout << "\n"; }

		if (rev) // 틀린 이유..
			for(int i=1; i<=D; i++)
				A[i] = -A[i];
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0; i<com.size(); i++)
      |                ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 17