oj.uz

Submission #66169

# Submission time Handle Problem Language Result Execution time Memory
66169 2018-08-09T23:48:21 Z Benq Sequence (BOI14_sequence) C++11
42 / 100
 1000 ms 2564 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,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];
    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 57 ms 1640 KB Output is correct
3 Correct 64 ms 1640 KB Output is correct
4 Correct 52 ms 1640 KB Output is correct
5 Correct 47 ms 1640 KB Output is correct
6 Correct 50 ms 1656 KB Output is correct
7 Correct 48 ms 1656 KB Output is correct
8 Correct 73 ms 1656 KB Output is correct
9 Correct 31 ms 1656 KB Output is correct
10 Correct 63 ms 1700 KB Output is correct
11 Correct 56 ms 1808 KB Output is correct
12 Correct 50 ms 1808 KB Output is correct
13 Correct 50 ms 1808 KB Output is correct
14 Correct 62 ms 1872 KB Output is correct
15 Correct 76 ms 1872 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1872 KB Output is correct
2 Correct 60 ms 1872 KB Output is correct
3 Correct 54 ms 1872 KB Output is correct
4 Correct 55 ms 1872 KB Output is correct
5 Correct 47 ms 1872 KB Output is correct
6 Correct 51 ms 1872 KB Output is correct
7 Correct 56 ms 1872 KB Output is correct
8 Correct 70 ms 1872 KB Output is correct
9 Correct 49 ms 1872 KB Output is correct
10 Correct 31 ms 1872 KB Output is correct
11 Correct 68 ms 1872 KB Output is correct
12 Correct 67 ms 1872 KB Output is correct
13 Correct 53 ms 1900 KB Output is correct
14 Correct 47 ms 1900 KB Output is correct
15 Correct 53 ms 1916 KB Output is correct
16 Correct 56 ms 1916 KB Output is correct
17 Correct 58 ms 1916 KB Output is correct
18 Correct 53 ms 1916 KB Output is correct
19 Correct 49 ms 1916 KB Output is correct
20 Correct 76 ms 1916 KB Output is correct
21 Correct 51 ms 1916 KB Output is correct
22 Correct 67 ms 1916 KB Output is correct
23 Correct 68 ms 1916 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1916 KB Output is correct
2 Correct 141 ms 1916 KB Output is correct
3 Correct 135 ms 1916 KB Output is correct
4 Correct 234 ms 1916 KB Output is correct
5 Correct 246 ms 1916 KB Output is correct
6 Correct 109 ms 1916 KB Output is correct
7 Correct 798 ms 2124 KB Output is correct
8 Correct 461 ms 2148 KB Output is correct
9 Execution timed out 1084 ms 2520 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2520 KB Output is correct
2 Correct 56 ms 2520 KB Output is correct
3 Correct 54 ms 2520 KB Output is correct
4 Correct 81 ms 2520 KB Output is correct
5 Correct 569 ms 2520 KB Output is correct
6 Correct 51 ms 2520 KB Output is correct
7 Correct 52 ms 2520 KB Output is correct
8 Correct 57 ms 2520 KB Output is correct
9 Correct 51 ms 2520 KB Output is correct
10 Correct 51 ms 2520 KB Output is correct
11 Execution timed out 1016 ms 2564 KB Time limit exceeded
12 Halted 0 ms 0 KB -