oj.uz

답안 #345490

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

int a[DIM],aux[DIM],aux2[DIM],sol[DIM],ans[DIM],st[DIM],dr[DIM],mid[DIM],unu[3];
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] / 10;
        c[i] %= 10;
    }

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

}

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] / 10;
        c[i] %= 10;
    }

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

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

    int r = 0;
    for (int i=a[0];i;i--){
        r = r * 10 + 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] += 10;
    }

    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;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];
}

void scadere1 (int a[]){

    int i = 1;
    while (i <= a[0] && !a[i]){
        a[i] = 9;
        i++;
    }

    a[i]--;
    if (i == a[0] && !a[i])
        a[0]--;

}

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++)
        a[n-i+1] = dr[n-i+1] = s[i] - '0';
    a[0] = dr[0] = n;

    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;
    }

    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);
            scadere1 (dr);
        }

    }

    copiere (aux,sol);
    scadere1 (aux);


    inmultire (aux,sol,ans);
    adunare (ans,sol,ans);
    adunare (ans,unu,ans);


    /// mai adun ce a mai ramas din ultima grupa

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

    scadere (a,aux);

    scadere1 (a);

    adunare (ans,a,ans);
    adunare (ans,a,ans);

    for (i=ans[0];i;i--)
        cout<<ans[i];



    return 0;
}

Compilation message

oddeven.cpp: In function 'int main()':
oddeven.cpp:131:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |     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 1 ms 364 KB Output is correct
11 Execution timed out 2035 ms 364 KB Time limit exceeded
12 Halted 0 ms 0 KB -