Submission #118686

#	Time	Username	Problem	Language	Result	Execution time	Memory
118686		imyujin	Sequence (BOI14_sequence)	C++14	100 / 100	199 ms	1908 KiB

sequence

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

using namespace std;

#define MAXK 100005

const long long LINF=1ll<<58;
int B[MAXK];
int cnt;
bool p=false;

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

	if(p){
	printf("(");
	for(int i=0; i<v.size(); i++){
		for(int j=9; j>=0; j--) printf("%d", (v[i]>>j)&1);
		printf("\n");
	}
	}

	//if(cnt==100) return ans;
	//cnt++;

	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){
		if(p)printf(")))))))))*\n");
		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;
		if(p)printf("%lld*\n", ans);
		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){
			if(p)printf("))))))))\n");
			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);
		if(p){
		printf("\n");
		for(int i=0; i<v.size(); i++){
			for(int j=9; j>=0; j--) printf("%d", (v[i]>>j)&1);
			printf("\n");
		}
		printf("%d[%lld]\n", i, ans);
		}
	}
	if(p){
	printf("\n");
	for(int i=0; i<v.size(); i++){
		for(int j=9; j>=0; j--) printf("%d", (v[i]>>j)&1);
		printf("\n");
	}
	printf(")%lld\n", ans);
	}
	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:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
sequence.cpp:29: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:46: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:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
sequence.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                ~^~~~~~~~~
sequence.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &K);
  ~~~~~^~~~~~~~~~
sequence.cpp:90: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