oj.uz

Submission #474949

# Submission time Handle Problem Language Result Execution time Memory
474949 2021-09-20T10:18:49 Z cs71107 Sequence (BOI14_sequence) C++14
25 / 100
 38 ms 1356 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
int vv[20][MAXN];

ll solve(int t,int n){

    ll res = LINF;

    if(n==1){

        int curv = vv[t][0];

        if(curv&1){

            if(curv==1){
                res = 10;
            }
            else {

                res = 0;

                for(int i=1;i<10;i++){
                    if((1<<i)&curv){
                        if(!res){
                            res = (i*10);
                        }
                        else {
                            res = 10LL*res+i;
                        }
                    }
                }
            }
        }
        else {

            res = 0;

            for(int i=1;i<10;i++){
                if((1<<i)&curv){
                    res = 10LL*res+i;
                }
            }
        }

    }
    else if(n==2){

        res = LINF;

        int a,b;
        ll curres = LINF;

        for(int i=0;i<9;i++){
            a = vv[t][0]&(1023^(1<<i));
            b = vv[t][1]&(1023^(1<<(i+1)));
            vv[t+1][0] = a|b;

            curres = solve(t+1,1);

            if(curres){
                res = min(res,curres*10LL+i);
            }
            else if((!i)&&(vv[t][0]&1)){
                res = min(res,10LL);
            }
            else {
                res = min(res,(ll)i);
            }
        }

        if((vv[t][0]&512)||(vv[t][1]&1)){

            a = vv[t][0]&511;
            b = vv[t][1]&1022;
            vv[t+1][0] = a;
            vv[t+1][1] = b;

            curres = solve(t+1,2);

            res = min(res,curres*10LL+9);
        }

    }
    else {

        int cnt = 0;
        int idx = 0;
        int cur;
        ll curans = LINF;

        for(int tt=0;tt<10;tt++){

            cnt = 0;
            idx = tt;
            vv[t+1][0] = 0;

            for(int i=0;i<n;i++){

                cur = vv[t][i]&(1023^(1<<idx));

                vv[t+1][cnt]|=cur;

                idx++;
                if(idx==10){
                    idx = 0;
                    cnt++;
                    vv[t+1][cnt] = 0;
                }
            }

            if(idx){
                curans = solve(t+1,cnt+1);
            }
            else {
                curans = solve(t+1,cnt);
            }

            //cout<<t<<" "<<curans<<"\n";

            res = min(res,curans*10LL+tt);
        }

    }

    return res;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }

    for(int i=0;i<n;i++){
        vv[0][i] = (1<<A[i]);
    }

    ll res = solve(0,n);

    cout<<res<<"\n";


    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:150:11: warning: unused variable 'm' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |           ^
sequence.cpp:150:13: warning: unused variable 'k' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |             ^
sequence.cpp:150:15: warning: unused variable 'a' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |               ^
sequence.cpp:150:17: warning: unused variable 'b' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |                 ^
sequence.cpp:150:19: warning: unused variable 'x' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |                   ^
sequence.cpp:150:21: warning: unused variable 'y' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |                     ^
sequence.cpp:150:23: warning: unused variable 'q' [-Wunused-variable]
  150 |     int n,m,k,a,b,x,y,q;
      |                       ^
sequence.cpp:151:9: warning: unused variable 'sum' [-Wunused-variable]
  151 |     int sum = 0;
      |         ^~~
sequence.cpp:152:9: warning: unused variable 'cnt' [-Wunused-variable]
  152 |     int cnt = 0;
      |         ^~~
sequence.cpp:153:9: warning: unused variable 'mx' [-Wunused-variable]
  153 |     int mx = 0;
      |         ^~
sequence.cpp:154:9: warning: unused variable 'mn' [-Wunused-variable]
  154 |     int mn = INF;
      |         ^~
sequence.cpp:155:9: warning: unused variable 'cur' [-Wunused-variable]
  155 |     int cur = 0, idx = -1;
      |         ^~~
sequence.cpp:155:18: warning: unused variable 'idx' [-Wunused-variable]
  155 |     int cur = 0, idx = -1;
      |                  ^~~
sequence.cpp:156:9: warning: unused variable 'tc' [-Wunused-variable]
  156 |     int tc;
      |         ^~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 33.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 472 KB Output is correct
3 Correct 6 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 26 ms 972 KB Output is correct
8 Correct 23 ms 716 KB Output is correct
9 Correct 35 ms 1356 KB Output is correct
10 Correct 38 ms 1356 KB Output is correct

Subtask #4
0 / 33.0

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