oj.uz

Submission #824771

# Submission time Handle Problem Language Result Execution time Memory
824771 2023-08-14T09:54:36 Z QwertyPi Sequence (BOI14_sequence) C++14
0 / 100
 1000 ms 428 KB 
#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){
	// cout << "QUERY " << base << ' ' << geq1 << ' ' << pw10 << endl;
	// cout << "a[] "; for(auto i : a) cout << i << ' '; cout << endl;
	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 a1 = brute(a);
	int a2 = clever(a);
	cout << a1 << ' ' << a2 << endl;
	assert(a1 == a2);
	// cout << ans << endl;
}

Compilation message

sequence.cpp: In function 'long long int query(long long int, bool, bool, long long int, std::vector<long long int>)':
sequence.cpp:29: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]
   29 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
sequence.cpp: In function 'long long int brute(std::vector<long long int>)':
sequence.cpp:61: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]
   61 |   for(int j = 0; j < a.size(); j++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1070 ms 428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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