oj.uz

Submission #718793

# Submission time Handle Problem Language Result Execution time Memory
718793 2023-04-04T20:26:37 Z edenooo Weird Numeral System (CCO21_day1problem2) C++17
8 / 25
 1012 ms 12460 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[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

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 480 ms 12184 KB OK
2 Correct 681 ms 12312 KB OK
3 Correct 746 ms 12376 KB OK
4 Correct 888 ms 12296 KB OK
5 Correct 904 ms 12332 KB OK
6 Correct 825 ms 12200 KB OK
7 Correct 959 ms 12296 KB OK
8 Correct 995 ms 12364 KB OK

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 12184 KB OK
2 Correct 681 ms 12312 KB OK
3 Correct 746 ms 12376 KB OK
4 Correct 888 ms 12296 KB OK
5 Correct 904 ms 12332 KB OK
6 Correct 825 ms 12200 KB OK
7 Correct 959 ms 12296 KB OK
8 Correct 995 ms 12364 KB OK
9 Correct 1012 ms 12340 KB OK
10 Correct 654 ms 12336 KB OK
11 Correct 959 ms 12460 KB OK
12 Correct 984 ms 12404 KB OK
13 Correct 939 ms 12216 KB OK
14 Correct 934 ms 12376 KB OK
15 Correct 960 ms 12336 KB OK
16 Incorrect 489 ms 11836 KB Query 1: Jury has an answer but participant does not
17 Halted 0 ms 0 KB -