oj.uz

Submission #413307

# Submission time Handle Problem Language Result Execution time Memory
413307 2021-05-28T13:18:18 Z 송준혁(#7515) Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 1 ms 204 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

LL N;
int K, Q, M;
int A[5050], P[110];
vector<pii> D[110];

int main(){
	scanf("%d %d %d %*d", &K, &Q, &M);
	for (int i=1; i<=M; i++) scanf("%d", &A[i]);
	D[0].pb(pii(0,0));
	while (Q--){
		scanf("%lld", &N);
		int i;
		for (i=1; i<=80; i++){
			D[i].clear();
			int pv=MOD;
			P[i] = (N%K+K)%K;
			bool tf = false;
			for (pii t : D[i-1]){
				if (t.fi == pv) continue;
				if (t.fi == N && i > 1){
					tf = true;
					break;
				}
				for (int j=1; j<=M; j++) if (((t.fi+A[j])%K+K)%K == P[i]){
					D[i].pb(pii((t.fi+A[j]-P[i])/K, t.fi));
				}
				pv = t.fi;
			}
			if (tf) break;
			sort(all(D[i]));
			N = (N-P[i])/K;
		}
		pii pv = pii(MOD,0);
		i--;
		for (pii t : D[i]) if (t.fi == N) pv = t;
		if (pv.fi == MOD){
			puts("IMPOSSIBLE");
			continue;
		}
		for (i--; i>=0; i--){
			for (int j=1; j<=M; j++){
				if ((pv.se+A[j]-((pv.se+A[j])%K+K)%K)/K == pv.fi && ((pv.se+A[j])%K+K)%K == P[i+1]){
					printf("%d ", A[j]);
					break;
				}
			}
			for (pii t : D[i]) if (t.fi == pv.se){
				pv = t;
				break;
			}
		}
		printf("\n");
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d %d %d %*d", &K, &Q, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  for (int i=1; i<=M; i++) scanf("%d", &A[i]);
      |                           ~~~~~^~~~~~~~~~~~~
Main.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld", &N);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -