oj.uz

Submission #167220

# Submission time Handle Problem Language Result Execution time Memory
167220 2019-12-06T17:09:40 Z ryansee Sequence (BOI14_sequence) C++14
9 / 100
 7 ms 1016 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i, s, e) for(ll i=s;i<=ll(e);++i)
#define DEC(i, s, e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (100006)
ll n;
ll A[MAXN];
int main()
{
	FAST
	cin>>n;
	FOR(i,0,n-1)cin>>A[i];
	auto st3=[&]() {
	    auto gotzero=[&](ll x) {
	      while(x) {
	          if(x%10 == 0) return 1;
	          x /= 10;
	      }  
	      return 0;
	    };
	    auto all9=[&](ll n) {
	        ll on=n;
			ll val = 1;
			while(val*10 <= n) val*=10;
			n -= (n%val);
			FOR(i,n,on) {
			    if(!gotzero(i)) return 1;
			}
			return 0;
		};
		-- n;
		if(n==0) {
			return (A[0]==0?"1":"") + to_string(A[0]);
		}
		string lol = to_string(A[0]) + to_string(n);
		FOR(i,1,lol.size()-1) lol[i]='0';
		if(lol[0]=='0') {
			if(all9(n)) { lol='1'+lol; }
			else lol[0]='1';
		}
		if(A[0]==9) {
		    if(n%10==0 && rand(0, 2)) lol.pop_back();
			for(auto &i:lol) i='8';
			lol.back()='9';
		}
		return lol;
	};
	auto st1=[&]() {
		auto have=[&](ll x,ll y) {
			string X=to_string(x);
			char Y=y+48;
			return find(all(X), Y) != X.end();
		};
		FOR(i,1,1000) {
			bool no=0;
			ll co=i;
			FOR(j,0,n-1) {
				if(!have(co, A[j])) { no=1; break; }
				++ co;
			}
			if(no) {
				no=0;
				co=i;
				FOR(j,0,n-1) {
					if(co<0||!have(co, A[j])) { no=1; break; }
					-- co;
				}
			}
			if(!no) {
				return to_string(i);
			}
		}
		return (string) "***";
	};
	FOR(i,1,n-1) if(A[i]!=A[i-1]) { cout<<st1(); return 0; }
	cout<<st3(); return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 380 KB Output is correct

Subtask #2
0 / 33.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 33.0

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