oj.uz

Submission #437843

# Submission time Handle Problem Language Result Execution time Memory
437843 2021-06-27T07:42:19 Z ymm Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 16804 KB 
///
///    "Excuse me... What did you say about my hair?!"
///
///                                    -Josuke Higashikata

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
typedef vector<int> vec;

const int N = 200'010;
int a[N], c[N], l[N], r[N], v[N];
int n, q;

vec distribute_candies(vec cc, vec ll, vec rr, vec vv)
{
    n = cc.size();
    q = ll.size();
    while(q%2)
    {
        ++q;
        ll.push_back(0);
        rr.push_back(1);
        vv.push_back(0);
    }
    Loop(i,0,n) c[i] = cc[i];
    Loop(i,0,q) l[i] = ll[i], r[i] = rr[i], v[i] = vv[i];
    for(int i=0;i<q;i+=2)
    {
        int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;
        int v1=v[i+1], l1=l[i+1], r1=r[i+1]+1;
        if(false){}
        else if(l0<=r0&&r0<=l1&&l1<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=r0;j<l1;++j) {}
                if(v0>0 && v1<=0) for(int j=r0;j<l1;++j) {}
                if(v0<=0 && v1>0) for(int j=r0;j<l1;++j) {}
                if(v0>0 && v1>0) for(int j=r0;j<l1;++j) {}
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l0<=l1&&l1<=r0&&r0<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l0<=l1&&l1<=r1&&r1<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<l1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
        else if(l1<=l0&&l0<=r0&&r0<=r1&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=r0;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
        }
        else if(l1<=l0&&l0<=r1&&r1<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<l0;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l0;j<r1;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=r1;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
        else if(l1<=r1&&r1<=l0&&l0<=r0&&1){
                if(v0<=0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0>0 && v1<=0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1<0?0:a[j]+v1;}
                if(v0<=0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0>0 && v1>0) for(int j=l1;j<r1;++j) {a[j]=a[j]+v1>c[j]?c[j]:a[j]+v1;}
                if(v0<=0 && v1<=0) for(int j=r1;j<l0;++j) {}
                if(v0>0 && v1<=0) for(int j=r1;j<l0;++j) {}
                if(v0<=0 && v1>0) for(int j=r1;j<l0;++j) {}
                if(v0>0 && v1>0) for(int j=r1;j<l0;++j) {}
                if(v0<=0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1<=0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
                if(v0<=0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0<0?0:a[j]+v0;}
                if(v0>0 && v1>0) for(int j=l0;j<r0;++j) {a[j]=a[j]+v0>c[j]?c[j]:a[j]+v0;}
        }
    }
    vec ans(n);
    Loop(i,0,n) ans[i] = a[i];
    return ans;
}

/*int main()
{
    //auto ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11});
    //for(int x : ans) cout << x << ' ';
    vec c(200000, 1e9);
    vec l(200000, 0);
    vec r(200000, 199999);
    vec v(200000, 12);
    distribute_candies(c,l,r,v);
    /*printf("int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;\n");
    printf("int v1=v[i+1], l1=l[i+1], r1=r[i+1]+1;\n");
    printf("if(false){}\n");
    int p[4] = {0, 0, 1, 1};
    do
    {
        int a = 0;
        printf("else if(");
        Loop(i,0,4-1)
        {
            printf("%c%d",a&(1<<p[i])?'r':'l',p[i]);
            a ^= (1<<p[i]);
            printf("<=%c%d&&",a&(1<<p[i+1])?'r':'l',p[i+1]);
        }
        printf("1){\n");
        a = 0;
        Loop(i,0,4-1)
        {
            Loop(k,0,4)
            {
                printf("\tif(%s && %s) ", k&1? "v0>0": "v0<=0", k&2? "v1>0": "v1<=0");
                printf("for(int j=%c%d;",a&(1<<p[i])?'r':'l',p[i]);
                a ^= (1<<p[i]);
                printf("j<%c%d;++j) {",a&(1<<p[i+1])?'r':'l',p[i+1]);
                Loop(j,0,2)
                    if(a&(1<<j)){
                        if(k&(1<<j))
                            printf("a[j]=a[j]+v%d>c[j]?c[j]:a[j]+v%d;",j,j);
                        else
                            printf("a[j]=a[j]+v%d<0?0:a[j]+v%d;",j,j);
                    }
                printf("}\n");
                a ^= (1<<p[i]);
            }
            a ^= (1<<p[i]);
        }
        printf("}\n");
    }while(next_permutation(p, p+4));
}*/

Compilation message

candies.cpp:147:5: warning: "/*" within comment [-Wcomment]
  147 |     /*printf("int v0=v[i+0], l0=l[i+0], r0=r[i+0]+1;\n");
      |

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 440 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3572 ms 14040 KB Output is correct
2 Correct 3357 ms 14396 KB Output is correct
3 Correct 3313 ms 14388 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 107 ms 10072 KB Output is correct
3 Correct 93 ms 7708 KB Output is correct
4 Correct 2983 ms 14120 KB Output is correct
5 Correct 3160 ms 16796 KB Output is correct
6 Correct 3096 ms 16800 KB Output is correct
7 Correct 3034 ms 16804 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 118 ms 9944 KB Output is correct
4 Correct 113 ms 5536 KB Output is correct
5 Execution timed out 5011 ms 13908 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 440 KB Output is correct
6 Correct 3572 ms 14040 KB Output is correct
7 Correct 3357 ms 14396 KB Output is correct
8 Correct 3313 ms 14388 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 107 ms 10072 KB Output is correct
11 Correct 93 ms 7708 KB Output is correct
12 Correct 2983 ms 14120 KB Output is correct
13 Correct 3160 ms 16796 KB Output is correct
14 Correct 3096 ms 16800 KB Output is correct
15 Correct 3034 ms 16804 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 118 ms 9944 KB Output is correct
19 Correct 113 ms 5536 KB Output is correct
20 Execution timed out 5011 ms 13908 KB Time limit exceeded
21 Halted 0 ms 0 KB -