oj.uz

Submission #437844

# Submission time Handle Problem Language Result Execution time Memory
437844 2021-06-27T07:43:29 Z ymm Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 11248 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("O3")
#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 2 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3486 ms 11192 KB Output is correct
2 Correct 3457 ms 11248 KB Output is correct
3 Correct 3387 ms 11248 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 110 ms 7492 KB Output is correct
3 Correct 90 ms 5388 KB Output is correct
4 Correct 3166 ms 11244 KB Output is correct
5 Correct 3049 ms 11248 KB Output is correct
6 Correct 3085 ms 11244 KB Output is correct
7 Correct 3074 ms 11244 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 121 ms 7384 KB Output is correct
4 Correct 113 ms 4412 KB Output is correct
5 Execution timed out 5097 ms 10436 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 2 ms 332 KB Output is correct
6 Correct 3486 ms 11192 KB Output is correct
7 Correct 3457 ms 11248 KB Output is correct
8 Correct 3387 ms 11248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 110 ms 7492 KB Output is correct
11 Correct 90 ms 5388 KB Output is correct
12 Correct 3166 ms 11244 KB Output is correct
13 Correct 3049 ms 11248 KB Output is correct
14 Correct 3085 ms 11244 KB Output is correct
15 Correct 3074 ms 11244 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 121 ms 7384 KB Output is correct
19 Correct 113 ms 4412 KB Output is correct
20 Execution timed out 5097 ms 10436 KB Time limit exceeded
21 Halted 0 ms 0 KB -