Submission #118735

#	Time	Username	Problem	Language	Result	Execution time	Memory
118735		onjo0127	Sequence (BOI14_sequence)	C++11	100 / 100	879 ms	1392 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

long long solve(vector<int> S, int dep, bool lzn) {
	if(dep >= 15) return -1;
	if(S.size() == 1) {
		if(lzn) {
			if(S[0] == 0) return 1;
			if(S[0] == 1) return 10;
		}
		long long ret = 0;
		for(int i=1; i<10; i++) if(S[0] & (1 << i)) {
			ret *= 10, ret += i;
			if(S[0] & 1) ret *= 10, --S[0];
		}
		return ret;
	}
	long long ret = 1LL * 1e18;
	for(int i=0; i<10; i++) {
		vector<int> N; int y = 0;
		for(int j=0, k=i; j<S.size(); j++, k++, k%=10) {
			if(j && !k) N.push_back(y), y = 0;
			y |= (S[j] & (~(1 << k)));
		}
		N.push_back(y);
		long long tmp = solve(N, dep + 1, N[0] != 0 || (lzn && i == 0));
		if(tmp != -1LL) ret = min(ret, tmp * 10 + i);
	}
	return ret;
}

int main() {
	vector<int> S;
	int K; scanf("%d",&K);
	for(int i=0; i<K; i++) {
		int foo; scanf("%d",&foo);
		S.push_back(1 << foo);
	}
	printf("%lld", solve(S, 1, 1));
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'long long int solve(std::vector<int>, int, bool)':
sequence.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0, k=i; j<S.size(); j++, k++, k%=10) {
                     ~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int K; scanf("%d",&K);
         ~~~~~^~~~~~~~~
sequence.cpp:36:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int foo; scanf("%d",&foo);
            ~~~~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33