oj.uz

Submission #118731

# Submission time Handle Problem Language Result Execution time Memory
118731 2019-06-19T14:17:30 Z onjo0127 Sequence (BOI14_sequence) C++11
0 / 100
 74 ms 768 KB 
#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(i && !k) N.push_back(y), y = 0;
			y |= (S[j] & (~(1 << k)));
		}
		N.push_back(y);
		if(N == S) continue;
		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, 0));
	return 0;
}

Compilation message

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:35: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:37: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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 74 ms 768 KB Output isn't correct
6 Halted 0 ms 0 KB -