oj.uz

Submission #824754

# Submission time Handle Problem Language Result Execution time Memory
824754 2023-08-14T09:37:09 Z QwertyPi Sequence (BOI14_sequence) C++14
0 / 100
 44 ms 1228 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) return base;
		if(a[0] == 0 && geq1) return pw10 + 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)){
				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;
}

int32_t main() {
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> c[i];
	}

	if(n == 1){
		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 ans = query(0, false, false, 1, a);
	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:28: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]
   28 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 44 ms 1228 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -