oj.uz

Submission #476756

# Submission time Handle Problem Language Result Execution time Memory
476756 2021-09-28T13:25:42 Z SamAnd Sequence (BOI14_sequence) C++17
25 / 100
 137 ms 1724 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const ll INF = 1000000009000000009;

int emp;
ll rec(vector<int> v)
{
    while (!v.empty() && v.back() == 0)
        v.pop_back();

    if (v.empty())
        return emp;
    if (sz(v) == 1)
    {
        ll ans = 0;
        if (!(v[0] & 1))
        {
            for (int i = 0; i < 10; ++i)
            {
                if ((v[0] & (1 << i)))
                    ans = (ans * 10 + i);
            }
        }
        else
        {
            bool z = false;
            for (int i = 1; i < 10; ++i)
            {
                if ((v[0] & (1 << i)))
                {
                    ans = (ans * 10 + i);
                    if (!z)
                    {
                        z = true;
                        ans = (ans * 10);
                    }
                }
            }
            if (!z)
                ans = 10;
        }
        return ans;
    }

    ll ans = INF;
    for (int s = 0; s < 10; ++s)
    {
        int x = s;
        vector<int> u = v;
        vector<int> nv;
        int j = 0;
        for (int i = 0; i < sz(u); ++i)
        {
            u[i] = (u[i] & (((1 << 10) - 1) ^ (1 << x)));
            if (x == 9)
            {
                int y = 0;
                while (j <= i)
                    y |= u[j++];
                nv.push_back(y);
            }
            x = (x + 1) % 10;
        }
        {
            int y = 0;
            while (j < sz(u))
                y |= u[j++];
            if (y)
                nv.push_back(y);
        }

        if (sz(v) == 2 && sz(nv) == 2 && v[0] == nv[0] && v[1] == nv[1])
            continue;
        ans = min(ans, rec(nv) * 10 + s);
    }

    return ans;
}

void solv()
{
    int n;
    cin >> n;
    vector<int> v;
    while (n--)
    {
        int x;
        cin >> x;
        v.push_back((1 << x));
    }

    ll ans = rec(v);
    if (!ans)
    {
        ans = 1;
        while (1)
        {
            bool z = true;
            int x = ans;
            for (int i = 0; i < sz(v); ++i)
            {
                bool zz = false;
                int y = x;
                while (y)
                {
                    if ((1 << y % 10) == v[i])
                    {
                        zz = true;
                        break;
                    }
                    y /= 10;
                }
                if (!zz)
                {
                    z = false;
                    break;
                }
                ++x;
            }
            if (z)
                break;
            ans *= 10;
        }
    }
    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
        solv();
    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 23 ms 460 KB Output is correct
3 Correct 24 ms 484 KB Output is correct
4 Correct 13 ms 460 KB Output is correct
5 Correct 14 ms 484 KB Output is correct
6 Correct 11 ms 448 KB Output is correct
7 Correct 95 ms 1228 KB Output is correct
8 Correct 107 ms 1016 KB Output is correct
9 Correct 128 ms 1724 KB Output is correct
10 Correct 137 ms 1648 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 127 ms 976 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Incorrect 2 ms 332 KB Output isn't correct
11 Halted 0 ms 0 KB -