Submission #718797

#	Time	Username	Problem	Language	Result	Execution time	Memory
718797		edenooo	Weird Numeral System (CCO21_day1problem2)	C++17	8 / 25	1323 ms	12856 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[60], suf[61]; // suf[i] : [i, ...]번째 자리가 전부 0인가?
vector<int> com;
int ord[1000000];
bitset<10001> X[5001];
bitset<10001> dp[61];
bitset<10001> ep;
int p[61][10001]; // 사용한 x값 (역추적용)

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

	int x = p[i][j];

	j -= 5000;
	f(i+1, (j+x-n[i] >= 0 ? (j+x-n[i])/K+5000 : -((-(j+x-n[i])+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<61; 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<60; i++)
		{
			n[i] = N % K;
			N /= K;
		}
		suf[60] = 1;
		for(int i=59; 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[60][5000] = 1;
		for(int i=59; 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=-5000; j<=5000; 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-n[i])만큼이 올림된다.
				int idx = (ep & ((j-n[i]) >= 0 ? (X[pos] << (j-n[i])) : (X[pos] >> -(j-n[i]))))._Find_first();
				dp[i][j+5000] = (idx < 10001);
				if (dp[i][j+5000]) p[i][j+5000] = (idx - (j-n[i]) - 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