oj.uz

Submission #659868

# Submission time Handle Problem Language Result Execution time Memory
659868 2022-11-19T14:57:35 Z Savu_Stefan_Catalin Remittance (JOI19_remittance) C++14
55 / 100
 186 ms 31564 KB 
#include <iostream>
#include <algorithm>
using namespace std;
long long e[1005005],i,ok1,ok2,a[1005005],b[1005005],n,d[1005005],pp[1001],f[1000005],p,ppp[1001],poz1,poz2,poz3;
void make()
{
    long long t=0,i;
    for (i=1;(i<=e[0]||t)&&i<=1005004;++i)
    {
        e[i]+=t;
        t=0;
        if (e[i]>=0) {t=e[i]/2; e[i]%=2;}
        else {t=(e[i]-1)/2; e[i]=(e[i]%2+2)%2;}
    }
    e[0]=i-1;
    if (i>1005000) e[0]=1,e[1]=-1;
    else while (e[e[0]]==0&&e[0]!=0) e[0]--;
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    ppp[0]=1;
  	for (i=1;i<=50;++i)
      ppp[i]=2*ppp[i-1];
    cin>>n;
    for (i=1;i<=n;++i)
    {
        cin>>a[i];
        if (a[i]!=0) ok1=1;
        cin>>b[i];
        if (b[i]!=0) ok2=1;
        d[i]=a[i]-b[i];
        e[i]=d[i];
    }
    e[0]=n;
    if (!ok1&&!ok2) {cout<<"Yes"; return 0;}
    else if (!ok2) {cout<<"No"; return 0;}
    make();
        if (n<=1000){
    while (true)
    {
                if (e[0]==0) { break;}
        if (e[e[0]]<0) {cout<<"No"; return 0;}
        if (e[1]==0) {pp[++pp[0]]=0; for (i=1;i<e[0];++i)  e[i]=e[i+1]; e[e[0]]=0; e[0]--;}
        else
        {
            pp[++pp[0]]=1;
            for (i=1;i<=n;++i)
                e[i]--;
            e[0]=max(e[0],n);
            make();
        }
    }
    reverse(pp+1,pp+pp[0]+1);
    for (i=1;i<=pp[0];++i)
    {
        if (pp[i]==0) p*=2;
        else p++;
    }}
    else
    {
        for (i=1;i<=100;++i)
        if (e[i]==0) poz1=i;
        poz2=e[0]-poz1+1;
        for (i=poz1+1;i<=poz2-1;--i)
        {
            if (e[i]==0) {cout<<"No"; return 0;}
        }
        for (i=1;i<=poz1;++i)
        {
            if (e[i]==e[poz2+i-1]) {cout<<"No"; return 0;}
        }
        for (i=1;i<=poz1;++i)
        {
            if (e[i]==1) {poz3=i; break;}
        }
        for (i=poz1;i>poz3;--i)
        {
            if (e[i]==0) p++;
            else p*=2;
        }
        for (i=poz3;i>=1;--i)
        {
            if (e[i]==1) p++;
            else p*=2;
        }
    }
    f[n]=p;
    for (i=n;i>=2;--i)
    {
        f[i-1]=f[i]*2-d[i];
        if (f[i-1]<0) {cout<<"No"; return 0;}
    }
    cout<<"Yes";
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 6 ms 8152 KB Output is correct
15 Correct 6 ms 8148 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 8148 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 6 ms 8104 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 6 ms 8148 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 6 ms 8152 KB Output is correct
15 Correct 6 ms 8148 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 8148 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 6 ms 8104 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 6 ms 8148 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 7 ms 8148 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 6 ms 8148 KB Output is correct
43 Correct 6 ms 8148 KB Output is correct
44 Correct 7 ms 8148 KB Output is correct
45 Correct 7 ms 8148 KB Output is correct
46 Correct 6 ms 8188 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 6 ms 8148 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 0 ms 340 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Correct 6 ms 8148 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 6 ms 8148 KB Output is correct
58 Correct 0 ms 340 KB Output is correct
59 Correct 0 ms 340 KB Output is correct
60 Correct 7 ms 8212 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 6 ms 8152 KB Output is correct
15 Correct 6 ms 8148 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 6 ms 8148 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 6 ms 8104 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 6 ms 8148 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct
33 Correct 7 ms 8148 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 6 ms 8148 KB Output is correct
43 Correct 6 ms 8148 KB Output is correct
44 Correct 7 ms 8148 KB Output is correct
45 Correct 7 ms 8148 KB Output is correct
46 Correct 6 ms 8188 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 6 ms 8148 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 0 ms 340 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Correct 6 ms 8148 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 6 ms 8148 KB Output is correct
58 Correct 0 ms 340 KB Output is correct
59 Correct 0 ms 340 KB Output is correct
60 Correct 7 ms 8212 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 186 ms 31564 KB Output is correct
64 Incorrect 110 ms 31544 KB Output isn't correct
65 Halted 0 ms 0 KB -