oj.uz

Submission #21878

# Submission time Handle Problem Language Result Execution time Memory
21878 2017-04-26T15:09:07 Z petrpan Sequence (BOI14_sequence) C++14
25 / 100
 606 ms 15728 KB 
#include <iostream> 
#include <cstdio>
#include <vector>

using namespace std;

#define For(i , a , b) for (int i = a , _b = b ; i <= _b ; ++i)
#define Ford(i , a  ,b) for (int i = a , _b = b : i >= _b ; --i)
#define Rep(i , n) for (int i = 0 , _n = n ; i < _n ; ++i)
#define sz(A) ((int)A.size())
#define LL(x) (x << 1)
#define RR(x) ((x << 1) | 1)

typedef pair<int , int> pt;

const int maxn = 100000 + 123;
int k;
vector<int> d;

void ReadData() {
	cin >> k;
	d.resize(k);
	Rep(i,k) cin >> d[i];
}

long long fromVector(vector<int> d) {
	if (sz(d) == 0) return 0;
	if (sz(d) == 1 && d[0] == 0) {
		return 10;
	}
	if (sz(d) >= 2 && d[0] == 0) {
		swap(d[0], d[1]);
	}
	long long res = 0;
	for (int i = 0; i < (int)d.size() ; i++) {
		res = res * 10 + d[i];
	}
	return res;
}

const long long INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000 + 123;

bool onbit(const int state, const int pos) {
	return ((state >> pos) & 1);
}
int offbit(const int state , const int pos) {
	return state ^ (1 << pos);
}

int total = 0;
long long solve(int pos, vector<vector<int> >  need) {
	if (sz(need) <= 1) {
		if (sz(need) == 0) return 0;
		return fromVector(need[0]);
	}

	long long res = INF;
	vector<int> f;
	f.resize(sz(need));
	for (int i = 0; i < (int)need.size(); ++i) {
		f[i] = 0;
		for (int x : need[i]) f[i] |= (1 << x);
	}
	for (int d = 0; d <= 9; ++d) {
		vector<vector<int> > to;
		bool ok = false;
		int k = d;
		vector<int> g = f;
		for (int i = 0; i < (int)need.size() ; i++) {
			int u = k % 10;
			if (onbit(g[i], u)) {
				g[i] = offbit(g[i],  u);
				ok = true;
			}
			k++;
		}  
		if (!ok) continue;
		vector<int> maskTo(k / 10 + 3, 0);
		k = d;
		for (int i = 0; i < (int)need.size(); i++) {
			maskTo[k / 10] |= g[i];
			k++;
		}
		For(z,0,k / 10) {
			to.push_back(vector<int>(0));
			vector<int> &a = to.back();
			For(l, 0, 9) if (onbit(maskTo[z], l)) a.push_back(l);
		}
		while (sz(to) && sz(to.back()) == 0) to.pop_back();
		long long t = solve(pos + 1, to) * 10 + d;
		if (t == 0 && pos == 1) t = 10;
		res = min(res, t);
	}

	return res;
}

void Process() {
	vector<vector<int> > a(k);
	Rep(i,k) {
		a[i].push_back(d[i]);
	}
	cout << solve(1, a) << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//freopen("input.inp" , "r" , stdin);
	ReadData();
	Process(); 

	return 0;

}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2184 KB Output is correct
2 Correct 29 ms 3676 KB Output is correct
3 Correct 26 ms 3676 KB Output is correct
4 Correct 26 ms 3676 KB Output is correct
5 Correct 26 ms 3676 KB Output is correct
6 Correct 19 ms 3240 KB Output is correct
7 Correct 173 ms 11516 KB Output is correct
8 Correct 169 ms 8396 KB Output is correct
9 Correct 263 ms 15728 KB Output is correct
10 Correct 286 ms 15728 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2184 KB Output is correct
2 Correct 3 ms 2184 KB Output is correct
3 Correct 0 ms 2184 KB Output is correct
4 Correct 0 ms 2184 KB Output is correct
5 Correct 606 ms 8212 KB Output is correct
6 Correct 0 ms 2184 KB Output is correct
7 Correct 0 ms 2184 KB Output is correct
8 Correct 0 ms 2316 KB Output is correct
9 Correct 0 ms 2184 KB Output is correct
10 Incorrect 0 ms 2316 KB Output isn't correct
11 Halted 0 ms 0 KB -