oj.uz

Submission #718795

# Submission time Handle Problem Language Result Execution time Memory
718795 2023-04-04T20:40:28 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 1491 ms 13452 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[120], suf[121]; // suf[i] : [i, ...]번째 자리가 전부 0인가?
vector<int> com;
int ord[1000000];
bitset<10001> X[5001];
bitset<10001> dp[121];
bitset<10001> ep;
int p[121][10001]; // 사용한 x값 (역추적용)

void f(int i, int j) // backtrack
{
	if (i == 120) 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<121; 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<120; i++)
		{
			n[i] = N % K;
			N /= K;
		}
		suf[120] = 1;
		for(int i=119; 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[120][5000] = 1;
		for(int i=119; 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 737 ms 13176 KB OK
2 Correct 1055 ms 13240 KB OK
3 Correct 1147 ms 13316 KB OK
4 Correct 1254 ms 13288 KB OK
5 Correct 1227 ms 13364 KB OK
6 Correct 1192 ms 13188 KB OK
7 Correct 1491 ms 13292 KB OK
8 Correct 1445 ms 13280 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 13176 KB OK
2 Correct 1055 ms 13240 KB OK
3 Correct 1147 ms 13316 KB OK
4 Correct 1254 ms 13288 KB OK
5 Correct 1227 ms 13364 KB OK
6 Correct 1192 ms 13188 KB OK
7 Correct 1491 ms 13292 KB OK
8 Correct 1445 ms 13280 KB OK
9 Correct 1392 ms 13332 KB OK
10 Correct 979 ms 13336 KB OK
11 Correct 1489 ms 13400 KB OK
12 Correct 1408 ms 13452 KB OK
13 Correct 1385 ms 13216 KB OK
14 Correct 1380 ms 13332 KB OK
15 Correct 1398 ms 13388 KB OK
16 Incorrect 752 ms 12864 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -