oj.uz

Submission #718798

# Submission time Handle Problem Language Result Execution time Memory
718798 2023-04-04T21:10:38 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 2500 ms 18992 KB 
#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<20001> X[5001];
bitset<20001> dp[61];
bitset<20001> 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<=20000; j++)
				ep[j] = (j-10000 >= 0 ? dp[i+1][(j-10000)/K+5000] : dp[i+1][-((-(j-10000)+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]+5000) >= 0 ? (X[pos] << (j-n[i]+5000)) : (X[pos] >> -(j-n[i]+5000))))._Find_first();
				dp[i][j+5000] = (idx < 20001);
				if (dp[i][j+5000]) p[i][j+5000] = (idx - (j-n[i]) - 10000);
			}
		}

		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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 18760 KB OK
2 Correct 1717 ms 18872 KB OK
3 Correct 1920 ms 18964 KB OK
4 Correct 2093 ms 18864 KB OK
5 Correct 2128 ms 18904 KB OK
6 Correct 2284 ms 18992 KB OK
7 Execution timed out 2568 ms 18880 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 18760 KB OK
2 Correct 1717 ms 18872 KB OK
3 Correct 1920 ms 18964 KB OK
4 Correct 2093 ms 18864 KB OK
5 Correct 2128 ms 18904 KB OK
6 Correct 2284 ms 18992 KB OK
7 Execution timed out 2568 ms 18880 KB Time limit exceeded
8 Halted 0 ms 0 KB -