Submission #824774

#	Time	Username	Problem	Language	Result	Execution time	Memory
824774		QwertyPi	Sequence (BOI14_sequence)	C++14	100 / 100	118 ms	3184 KiB

sequence

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

const int MAXK = 1e5 + 11;
char c[MAXK];

int query(int base, bool geq1, bool prv2, int pw10, vector<int> a){
	if(a.size() == 1){
		if(a[0] == 0 && base == 0) return pw10;
		if(a[0] == 0 && geq1) return pw10 + base;
		if(a[0] == 0) return base;
		if(a[0] == 1) return 10 * pw10 + base;
		if(a[0] & 1){
			int fi = 1; while(!(a[0] & (1 << fi))) fi++;
			int r = fi * 10;
			for(int i = fi + 1; i < 10; i++) if(a[0] & (1 << i)) r = r * 10 + i;
			return r * pw10 + base;
		}else{
			int r = 0; for(int i = 1; i < 10; i++) if(a[0] & (1 << i)) r = r * 10 + i;
			return r * pw10 + base;
		}
	}
	int res = 1LL << 60;
	for(int c0 = 0; c0 <= 9 - prv2; c0++){
		vector<int> b {0}; bool n_geq1 = false;
		for(int i = 0; i < a.size(); i++){
			int g = c0 + i;
			if(g > 0 && g % 10 == 0){
				b.push_back(0);
			}
			int v = a[i]; 
			if(c0 == 0 && i == 0 && (a[i] & 1)){
				n_geq1 = true;
			}
			v -= v & (1 << g % 10);
			b.back() |= v;
		}
		res = min(res, query(base + pw10 * c0, n_geq1, a.size() == 2, pw10 * 10, b));
	}
	return res;
}

int clever(vector<int> a){
	return query(0, false, false, 1, a);
}

int cc(int x){
	int r = 0;
	while(x != 0){
		r |= (1 << x % 10);
		x /= 10;
	}
	return r;
}
int brute(vector<int> a){
	for(int i = 1;; i++){
		bool ok = true;
		for(int j = 0; j < a.size(); j++){
			ok &= (cc(i + j) & a[j]) == a[j];
		}
		if(ok) return i;
	}
}
int32_t main() {
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> c[i];
	}

	if(n == 1){
		if(c[0] == '0'){
			cout << "10" << endl;
		}else{
			cout << c[0] << endl;
		}
		return 0;
	}

	vector<int> a;
	for(int i = 0; i < n; i++){
		int st = 1 << (c[i] - '0');
		a.push_back(st);
	}

	int a2 = clever(a);
	cout << a2 << endl;
}

Compilation message (stderr)

sequence.cpp: In function 'long long int query(long long int, bool, bool, long long int, std::vector<long long int>)':
sequence.cpp:27:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
sequence.cpp: In function 'long long int brute(std::vector<long long int>)':
sequence.cpp:59:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(int j = 0; j < a.size(); j++){
      |                  ~~^~~~~~~~~~

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