Submission #995751

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	int n;
	cin >> n;
	LL a[n];
	for(int i = 0; i < n; i++) cin >> a[i];
	LL ansnum = 0;

	vector<pair<LL,LL> > ans[n+1];
	vector<pair<LL,LL> > cur;


	for(int k = 17; k > 0; k--){
		LL r = 1;
		for(int c = 0; c < k; c++) r *= 10;
		LL p = r/10;
		for(int f = 1; f <= 9; f++){
			for(int i = 0; i <= n; i++) ans[i].clear();
			ans[0].push_back(make_pair(f*p,r-1));
			//cout << "case " << f*p << " " << r-1 << endl;
			int done = 0;
			for(int i = 0; i < n; i++){
				cur = ans[i];
				for(int l = 0; l < ans[i].size(); l++){
					if(a[i]%r >= ans[i][l].first && a[i]%r <= ans[i][l].second){
						done = 1;
						break;
					}
					LL s1 = (r+ans[i][l].first - a[i] % r)%r;
					LL e1 = (r+ans[i][l].second - a[i] % r)%r;
					cur.push_back(make_pair(s1,e1));
					//cout << s1 << " " << e1 << endl;
					if(done) break;
				}
				if(done) break;

				sort(cur.begin(), cur.end());
				/*for(int z = 0; z < cur.size(); z++){
					cout << cur[z].first << "," << cur[z].second << " ";
				}
				cout << endl;*/
				LL curs = 1e18;
				LL cure = -1;
				for(int z = 0; z < cur.size(); z++){
					if((!(cure < cur[z].first) && !(cur[z].second < curs)) || cure == -1){
						cure = max(cure,cur[z].second);
						curs = min(curs,cur[z].first);
					} else {
						ans[i+1].push_back(make_pair(curs,cure));
						curs = cur[z].first;
						cure = cur[z].second;
					}
				}
				if(cure != -1) ans[i+1].push_back(make_pair(curs,cure));

				/*for(int z = 0; z < ans[i+1].size(); z++){
					cout << ans[i+1][z].first << "," << ans[i+1][z].second << " ";
				}
				cout << endl;*/

				if(done) break;
			}
			if(done){
				ansnum ++;
				//cout << f*p << endl;
			}
		}
	}
	cout << ansnum << endl;
}

Submission Info

Judge Result