Submission #118713

#	Time	Username	Problem	Language	Result	Execution time	Memory
118713		sebinkim	Sequence (BOI14_sequence)	C++14	100 / 100	100 ms	1784 KiB

sequence

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll n;
 
ll f(vector <ll> &X, ll d, bool z)
{
	if(d > 14) return -1;
	
	vector <ll> Y;
	ll i, j, k, y, ret = 1e18;
	
	if(X.size() == 1){
		if(z && X[0] == 0) return 1;
		else if(z && X[0] == 1) return 10;
		
		ret = 0;
		
		for(i=1; i<10; i++){
			if(X[0] & (1ll << i)){
				ret = ret * 10 + i;
				if(X[0] & 1ll){
					ret *= 10; X[0] -= 1;
				}
			}
		}
		
		return ret;
	}
	
	for(i=0; i<10; i++){
		Y.clear(); y = 0;
		
		for(j=0, k=i; j<X.size(); j++, k=++k%10){
			if(k == 0 && j) Y.push_back(y), y = 0;
			
			if(X[j] & (1ll << k)) y |= X[j] - (1ll << k);
			else y |= X[j];
		}
		
		Y.push_back(y);
		
		if(X == Y) continue;
		
		k = f(Y, d + 1, Y[0] != 0 || (z && i == 0)) * 10 + i;
		if(k >= 0) ret = min(ret, k);
	}
	
	return ret;
}
 
int main()
{
	vector <ll> X;
	ll i, x;
	
	scanf("%lld", &n);
	
	for(i=0; i<n; i++){
		scanf("%lld", &x);
		X.push_back(1ll << x);
	}
	
	printf("%lld\n", f(X, 1, 1));
	
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'll f(std::vector<long long int>&, ll, bool)':
sequence.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, k=i; j<X.size(); j++, k=++k%10){
                 ~^~~~~~~~~
sequence.cpp:37:35: warning: operation on 'k' may be undefined [-Wsequence-point]
   for(j=0, k=i; j<X.size(); j++, k=++k%10){
                                  ~^~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
sequence.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

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