oj.uz

Submission #66170

# Submission time Handle Problem Language Result Execution time Memory
66170 2018-08-09T23:54:58 Z Benq Sequence (BOI14_sequence) C++11
67 / 100
 84 ms 10472 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const ll INF = 1e18;
const int MX = 100000;

ll ans = INF;
bitset<MX> bad[10], res[10], res2[10];
bitset<MX> BAD, RES, RES2;
int K, B[MX], digYes[MX], digNo[MX];

int match(int x, int y) {
    while (x) {
        if (x % 10 == y) return 1;
        x /= 10;
    }
    return 0;
}

ll tri(int x, int y) {
    if (x == 0) return y;
    if (x == 1) x ^= 2;
    ll t = 0;
    FOR(i,1,10) if (x&(1<<i)) {
        t = i;
        x ^= 1<<i;
        break;
    }
    F0R(i,10) if (x&(1<<i)) {
        t = 10*t+i;
        x ^= 1<<i;
    }
    return t;
}

ll solve(pi a, pi b) { // what about leading zeroes??
    ll t = INF;
    F0R(i,9) {
        int A = min(a.f,a.f^(1<<i));
        int B = min(b.f,b.f^(1<<(i+1)));
        t = min(t,10*tri(A|B,(a.f&1) || (i == 0 && a.s))+i);
        
        A = min(A,A^(1<<9));
        B = min(B,B^(1<<0));
        t = min(t,100*tri(A|B,a.s)+10*i+9);
    }
    return MX*t;
}

pi get0(int st) {
    pi ret = {0,0};
    F0R(i,10) if (res[i][st] == 1) ret.f ^= 1<<i;
    if (RES[st] == 1) ret.s = 1;
    return ret;
}

pi get1(int st) {
    pi ret = {0,0};
    F0R(i,10) if (res2[i][st] == 1) ret.f ^= 1<<i;
    if (RES2[st] == 1) ret.s = 1;
    return ret;
}

ll test(int st) {
    pi a = get0(st), b = get1(st);
    // if (st == 0) cout << a.f << " " << a.s << "\n";
    ll ret = st+solve(a,b);
    return ret;
}

void gen() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    FOR(i,1,MX) digNo[i] = digNo[i/10]|(1<<(i%10));
    F0R(i,MX) {
        digYes[i] = digNo[i];
        if (i < MX/10) digYes[i] |= 1;
    }
    
    F0R(i,MX) F0R(j,10) {
        if (!(digYes[i]&(1<<j))) bad[j][i] = 1;
        if (j == 0 && !(digNo[i]&(1<<j))) BAD[i] = 1;
    }
    
    cin >> K;
    F0R(i,K) cin >> B[i];
}

int main() {
    gen();
    if (K <= 1000) {
        F0R(i,K) {
            res[B[i]] |= (bad[B[i]]>>i);
            res2[B[i]] |= (bad[B[i]]<<(MX-i));
            if (B[i] == 0) {
                RES |= (BAD>>i);
                RES2 |= (BAD<<(MX-i));
            }
        }
        F0R(i,MX) ans = min(ans,test(i));
        cout << ans;
    } else {
        vi v = {0}; FOR(i,1,1100001) v.pb(match(i,B[0])+v.back());
        FOR(i,K,sz(v)) if (v[i] == v[i-K]+K) {
            cout << i-K+1;
            exit(0);
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1528 KB Output is correct
2 Correct 71 ms 1764 KB Output is correct
3 Correct 48 ms 1840 KB Output is correct
4 Correct 57 ms 1924 KB Output is correct
5 Correct 45 ms 1924 KB Output is correct
6 Correct 54 ms 1924 KB Output is correct
7 Correct 57 ms 1924 KB Output is correct
8 Correct 74 ms 1924 KB Output is correct
9 Correct 30 ms 1924 KB Output is correct
10 Correct 52 ms 1924 KB Output is correct
11 Correct 51 ms 1924 KB Output is correct
12 Correct 59 ms 1924 KB Output is correct
13 Correct 55 ms 1924 KB Output is correct
14 Correct 61 ms 1924 KB Output is correct
15 Correct 66 ms 1924 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 1924 KB Output is correct
2 Correct 68 ms 1924 KB Output is correct
3 Correct 47 ms 1924 KB Output is correct
4 Correct 48 ms 1924 KB Output is correct
5 Correct 60 ms 1924 KB Output is correct
6 Correct 46 ms 1924 KB Output is correct
7 Correct 52 ms 1924 KB Output is correct
8 Correct 51 ms 1924 KB Output is correct
9 Correct 49 ms 1924 KB Output is correct
10 Correct 28 ms 1924 KB Output is correct
11 Correct 75 ms 1924 KB Output is correct
12 Correct 65 ms 1924 KB Output is correct
13 Correct 55 ms 1924 KB Output is correct
14 Correct 62 ms 1924 KB Output is correct
15 Correct 48 ms 1924 KB Output is correct
16 Correct 62 ms 1924 KB Output is correct
17 Correct 84 ms 1924 KB Output is correct
18 Correct 49 ms 1924 KB Output is correct
19 Correct 52 ms 1924 KB Output is correct
20 Correct 59 ms 1924 KB Output is correct
21 Correct 44 ms 1924 KB Output is correct
22 Correct 59 ms 1924 KB Output is correct
23 Correct 61 ms 1924 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1924 KB Output is correct
2 Correct 28 ms 9956 KB Output is correct
3 Correct 32 ms 9956 KB Output is correct
4 Correct 32 ms 9956 KB Output is correct
5 Correct 29 ms 9956 KB Output is correct
6 Correct 29 ms 9956 KB Output is correct
7 Correct 39 ms 10084 KB Output is correct
8 Correct 32 ms 10084 KB Output is correct
9 Correct 35 ms 10196 KB Output is correct
10 Correct 40 ms 10472 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10472 KB Output is correct
2 Correct 52 ms 10472 KB Output is correct
3 Correct 72 ms 10472 KB Output is correct
4 Correct 57 ms 10472 KB Output is correct
5 Incorrect 42 ms 10472 KB Output isn't correct
6 Halted 0 ms 0 KB -