oj.uz

Submission #66168

# Submission time Handle Problem Language Result Execution time Memory
66168 2018-08-09T23:42:33 Z Benq Sequence (BOI14_sequence) C++11
42 / 100
 1000 ms 2376 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];

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,0)+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);
    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];
    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));
        }
    }
}

int main() {
    gen();
    F0R(i,MX) ans = min(ans,test(i));
    cout << ans;
}

/* 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 46 ms 1400 KB Output is correct
2 Correct 51 ms 1640 KB Output is correct
3 Correct 47 ms 1640 KB Output is correct
4 Correct 49 ms 1780 KB Output is correct
5 Correct 43 ms 1780 KB Output is correct
6 Correct 54 ms 1780 KB Output is correct
7 Correct 52 ms 1780 KB Output is correct
8 Correct 47 ms 1780 KB Output is correct
9 Correct 28 ms 1780 KB Output is correct
10 Correct 54 ms 1780 KB Output is correct
11 Correct 51 ms 1780 KB Output is correct
12 Correct 69 ms 1780 KB Output is correct
13 Correct 46 ms 1780 KB Output is correct
14 Correct 55 ms 1840 KB Output is correct
15 Correct 58 ms 1840 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1840 KB Output is correct
2 Correct 50 ms 1840 KB Output is correct
3 Correct 48 ms 1840 KB Output is correct
4 Correct 49 ms 1840 KB Output is correct
5 Correct 41 ms 1840 KB Output is correct
6 Correct 52 ms 1900 KB Output is correct
7 Correct 74 ms 1900 KB Output is correct
8 Correct 49 ms 1900 KB Output is correct
9 Correct 52 ms 1900 KB Output is correct
10 Correct 28 ms 1900 KB Output is correct
11 Correct 68 ms 1928 KB Output is correct
12 Correct 57 ms 1928 KB Output is correct
13 Correct 75 ms 1928 KB Output is correct
14 Correct 53 ms 1928 KB Output is correct
15 Correct 49 ms 1928 KB Output is correct
16 Correct 53 ms 1928 KB Output is correct
17 Correct 51 ms 1928 KB Output is correct
18 Correct 48 ms 1928 KB Output is correct
19 Correct 47 ms 1928 KB Output is correct
20 Correct 51 ms 1928 KB Output is correct
21 Correct 46 ms 1928 KB Output is correct
22 Correct 58 ms 1928 KB Output is correct
23 Correct 54 ms 1928 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1928 KB Output is correct
2 Correct 150 ms 1928 KB Output is correct
3 Correct 156 ms 1928 KB Output is correct
4 Correct 252 ms 1928 KB Output is correct
5 Incorrect 233 ms 1928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1928 KB Output is correct
2 Correct 49 ms 2004 KB Output is correct
3 Correct 49 ms 2004 KB Output is correct
4 Correct 68 ms 2004 KB Output is correct
5 Correct 538 ms 2176 KB Output is correct
6 Correct 51 ms 2176 KB Output is correct
7 Correct 55 ms 2176 KB Output is correct
8 Correct 64 ms 2176 KB Output is correct
9 Correct 58 ms 2176 KB Output is correct
10 Correct 57 ms 2176 KB Output is correct
11 Execution timed out 1069 ms 2376 KB Time limit exceeded
12 Halted 0 ms 0 KB -