oj.uz

Submission #338739

# Submission time Handle Problem Language Result Execution time Memory
338739 2020-12-23T19:22:52 Z limabeans Sequence (BOI14_sequence) C++17
0 / 100
 21 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 8e18;




ll solve(vector<int> a, bool flag9=true) {
    int n = a.size();
    if (n==1) {
	ll res = 0;
	for (int x=1; x<=9; x++) {
	    if (a[0]>>x&1) {
		res=res*10 + x;
		if (res==x && (a[0]&1)) {
		    // x is first digit, and we need 0
		    res=res*10;
		}
	    }
	}
	if (res==0 && (a[0]&1)) {
	    res = 10; //only 0
	}
	return res;
    } else {

	ll lo = inf;
	// iterate over last digit
	for (int x=0; x<9+flag9; x++) {
	    int d = x;
	    int mask = 0;
	    vector<int> na;
	    bool zero = false;
	    for (int i=0; i<n; i++) {
		mask |= (a[i] & (1023 ^ (1<<d)));
		if (d==0 && (a[i]&1)) {
		    zero = true;
		}
		d = (d+1) % 10;
		if (d==0 || i==n-1) {
		    na.push_back(mask);
		}
	    }

	    ll cur = solve(na, !(n==2 && x==9))*10 + x;
	    if (cur==0 && zero) cur = 10;
	    lo = min(lo, cur);
	}

	return lo;
    }
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	int d;
	cin>>d;
	a[i] = (1<<d);
	
    }
    cout<<solve(a)<<endl;    
    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 18 ms 492 KB Output is correct
3 Correct 17 ms 492 KB Output is correct
4 Incorrect 21 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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