oj.uz

답안 #345534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345534 2021-01-07T14:37:49 Z nicolaalexandra 홀-짝 수열 (IZhO11_oddeven) C++14
0 / 100
 2000 ms 364 KB 
#include <bits/stdc++.h>
#define DIM 500
#define BASE 10000
using namespace std;

int a[DIM],aux[DIM],sol[DIM],ans[DIM],st[DIM],dr[DIM],mid[DIM],unu[3],v[DIM];
char s[DIM];
int i;

void adunare (int a[], int b[], int c[]){
    int m;
    if (a[0] > b[0]){
        m = a[0];
        for (int i=b[0]+1;i<=m;i++)
            b[i] = 0;
    } else {
        m = b[0];
        for (int i=a[0]+1;i<=m;i++)
            a[i] = 0;
    }

    int t = 0;
    for (int i=1;i<=m;i++){
        c[i] = a[i] + b[i] + t;
        t = c[i] / BASE;
        c[i] %= BASE;
    }

    c[0] = m;
    while (t){
        c[++c[0]] = t%BASE;
        t /= BASE;
    }

}

void inmultire (int a[], int b[], int c[]){

    for (int i=1;i<=a[0] + b[0];i++)
        c[i] = 0;

    c[0] = a[0] + b[0] - 1;
    for (int i=1;i<=a[0];i++)
        for (int j=1;j<=b[0];j++)
            c[i+j-1] += a[i] * b[j];

    int t = 0;
    for (int i=1;i<=c[0];i++){
        c[i] += t;
        t = c[i] / BASE;
        c[i] %= BASE;
    }

    while (t){
        c[++c[0]] = t%BASE;
        t /= BASE;
    }
}

void impartire (int a[], int b){

    int r = 0;
    for (int i=a[0];i>=1;i--){
        r = r * BASE + a[i];
        a[i] = r / b;
        r %= b;
    }

    while (a[0] > 1 && !a[a[0]])
        a[0]--;

}

void scadere (int a[], int b[]){ /// a - b
    for (int i=b[0]+1;i<=a[0];i++)
        b[i] = 0;

    int t = 0;
    for (int i=1;i<=a[0];i++){
        a[i] = a[i] - (b[i] + t);
        if (a[i] < 0)
            t = 1;
        else t = 0;
        if (t)
            a[i] += BASE;
    }

    while (a[0] > 1 && !a[a[0]])
        a[0]--;
}

int compare (int a[], int b[]){ /// a <= b
    if (a[0] < b[0])
        return 1;
    if (a[0] > b[0])
        return 0;

    for (int i=a[0];i>=1;i--){
        if (a[i] < b[i])
            return 1;
        if (a[i] > b[i])
            return 0;
    }
    return 2; /// egale
}

void copiere (int a[], int b[]){
    for (int i=0;i<=b[0];i++)
        a[i] = b[i];
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    /// dc iau tle:((

    cin>>s+1;
    int n = strlen (s+1);

    for (i=1;i<=n;++i)
        v[i] = s[i] - '0';

    for (i=n;i>=1;i-=4){
        int val;
        if (i >= 3)
            val = ((v[i-3] * 10 + v[i-2])*10 + v[i-1])*10 + v[i];
        else {
            if (i == 2)
                val = v[1] * 10 + v[2];
            else val = v[1];
        }

        a[++a[0]] = val;
    }

    if (n == 1 && a[1] == 1){
        cout<<1;
        return 0;
    }

    if (n == 1 && a[1] == 2){
        cout<<2;
        return 0;
    }

    if (n == 1 && a[1] == 3){
        cout<<4;
        return 0;
    }

    for (i=n/2+1;i>=1;i-=4){
        if (i >= 4)
            dr[++dr[0]] = 9999;
        else {
            if (i >= 3)
                dr[++dr[0]] = 999;
            else {
                if (i >= 2)
                    dr[++dr[0]] = 99;
                else dr[++dr[0]] = 9;
            }
        }
    }


    st[0] = st[1] = 1;

    //st[0] = st[1] = 1;
    unu[0] = unu[1] = 1;

    while (compare(st,dr)){

        adunare (st,dr,mid);
        impartire (mid,2);

        inmultire (mid,mid,aux);
        adunare (mid,aux,aux);
        impartire (aux,2);

        if (compare(aux,a) == 1){
            copiere (sol,mid);
            adunare (mid,unu,st);
            /// st = mid+1;
        } else { /// dr = mid-1;
            copiere (dr,mid);
            scadere (dr,unu);
        }

    }

    adunare (a,a,ans);
    scadere (ans,sol);
    scadere (ans,unu);

    cout<<ans[ans[0]];

    for (i=ans[0]-1;i>=1;--i){

        int x = ans[i], nr = 0;
        if (!x) nr = 1;
        while (x){
            nr++;
            x /= 10;
        }

        for (int j=nr+1;j<=4;++j)
            cout<<0;
        cout<<ans[i];
    }
    //for (i=ans[0];i;i--)
      //  cout<<ans[i];


    return 0;
}

Compilation message

oddeven.cpp: In function 'int main()':
oddeven.cpp:119:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |     cin>>s+1;
      |          ~^~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Execution timed out 2069 ms 364 KB Time limit exceeded
15 Halted 0 ms 0 KB -