Submission #474950

#	Time	Username	Problem	Language	Result	Execution time	Memory
474950		cs71107	Sequence (BOI14_sequence)	C++14	100 / 100	60 ms	1364 KiB

sequence

#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";

            if(curans){
                res = min(res,curans*10LL+tt);
            }
            else if((!tt)&&(vv[t][0]&1)){
                res = min(res,10LL);
            }
            else {
                res = min(res,(ll)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 (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:158:11: warning: unused variable 'm' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |           ^
sequence.cpp:158:13: warning: unused variable 'k' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |             ^
sequence.cpp:158:15: warning: unused variable 'a' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |               ^
sequence.cpp:158:17: warning: unused variable 'b' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |                 ^
sequence.cpp:158:19: warning: unused variable 'x' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |                   ^
sequence.cpp:158:21: warning: unused variable 'y' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |                     ^
sequence.cpp:158:23: warning: unused variable 'q' [-Wunused-variable]
  158 |     int n,m,k,a,b,x,y,q;
      |                       ^
sequence.cpp:159:9: warning: unused variable 'sum' [-Wunused-variable]
  159 |     int sum = 0;
      |         ^~~
sequence.cpp:160:9: warning: unused variable 'cnt' [-Wunused-variable]
  160 |     int cnt = 0;
      |         ^~~
sequence.cpp:161:9: warning: unused variable 'mx' [-Wunused-variable]
  161 |     int mx = 0;
      |         ^~
sequence.cpp:162:9: warning: unused variable 'mn' [-Wunused-variable]
  162 |     int mn = INF;
      |         ^~
sequence.cpp:163:9: warning: unused variable 'cur' [-Wunused-variable]
  163 |     int cur = 0, idx = -1;
      |         ^~~
sequence.cpp:163:18: warning: unused variable 'idx' [-Wunused-variable]
  163 |     int cur = 0, idx = -1;
      |                  ^~~
sequence.cpp:164:9: warning: unused variable 'tc' [-Wunused-variable]
  164 |     int tc;
      |         ^~

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33