Submission #118688

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

sequence

#include<stdio.h>
#include<vector>

using namespace std;

#define MAXK 100005

const long long LINF=1ll<<58;
int B[MAXK];

long long f(vector<int> v){
	vector<int> vv;
	long long ans=LINF;

	bool b=true;
	for(int i=0; i<v.size(); i++) if(v[i]!=0) b=false;
	if(b) return 0;

	if(v.size()==1){
		ans=0;
		int j=1;
		while((v[0]&(1<<j))==0&&j<10) j++;
		if(j==10) return (v[0]&1)==0?0ll:10ll;
		else ans=j;
		if((v[0]&1)!=0) ans*=10;
		for(j++; j<10; j++) if((v[0]&(1<<j))!=0) ans=ans*10+j;
		return ans;
	}
	for(int i=0; i<10; i++){
		bool a=true;
		for(int j=0; j<v.size(); j++) if(v[j]!=(1<<((i+j)%10))&&v[j]!=0) a=false;
		if(a) return i==0&&(v[0]&1)!=0?10ll:(long long)i;
	}
	
	for(int i=0; i<10; i++){
		int k=0;
		vv.clear();
		bool a=false;
		for(int j=0; j<v.size(); j++){
			if(j==0||(i+j)%10==0) vv.push_back(0);
			vv[k]|=(v[j]-(v[j]&(1<<((i+j)%10))));
			if(v[j]&(1<<((i+j)%10))) a=true;
			if((i+j)%10==9) k++;
		}
		if(a||vv.size()<v.size())
			ans=min(ans, f(vv)*10+i);
	}
	return ans;
}

int main(){
	int K;
	vector<int> v;
	
	scanf("%d", &K);
	for(int i=0; i<K; i++) scanf("%d", B+i);
	
	for(int i=0; i<K; i++) v.push_back(1<<B[i]);
	printf("%lld", f(v));
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'long long int f(std::vector<int>)':
sequence.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++) if(v[i]!=0) b=false;
               ~^~~~~~~~~
sequence.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++) if(v[j]!=(1<<((i+j)%10))&&v[j]!=0) a=false;
                ~^~~~~~~~~
sequence.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &K);
  ~~~~~^~~~~~~~~~
sequence.cpp:56:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<K; i++) scanf("%d", B+i);
                         ~~~~~^~~~~~~~~~~

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