oj.uz

Submission #718794

# Submission time Handle Problem Language Result Execution time Memory
718794 2023-04-04T20:36:50 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 741 ms 11984 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<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 >= 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<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=-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

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

# Verdict Execution time Memory Grader output
1 Correct 412 ms 11748 KB OK
2 Correct 540 ms 11720 KB OK
3 Correct 561 ms 11876 KB OK
4 Correct 601 ms 11788 KB OK
5 Correct 602 ms 11788 KB OK
6 Correct 601 ms 11864 KB OK
7 Correct 706 ms 11984 KB OK
8 Correct 741 ms 11880 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 11748 KB OK
2 Correct 540 ms 11720 KB OK
3 Correct 561 ms 11876 KB OK
4 Correct 601 ms 11788 KB OK
5 Correct 602 ms 11788 KB OK
6 Correct 601 ms 11864 KB OK
7 Correct 706 ms 11984 KB OK
8 Correct 741 ms 11880 KB OK
9 Correct 685 ms 11836 KB OK
10 Correct 484 ms 11852 KB OK
11 Correct 702 ms 11852 KB OK
12 Correct 706 ms 11852 KB OK
13 Correct 722 ms 11844 KB OK
14 Correct 677 ms 11836 KB OK
15 Correct 723 ms 11724 KB OK
16 Incorrect 384 ms 11488 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -