oj.uz

Submission #437815

# Submission time Handle Problem Language Result Execution time Memory
437815 2021-06-27T07:14:24 Z ymm Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 17156 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", "unroll-loops")
#pragma GCC target("avx")
typedef vector<int> vec;

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

#define Do(v) {a[j]=a[j]+v;a[j]=a[j]<0?0:a[j];a[j]=a[j]>c[j]?c[j]:a[j];}

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){
                for(int j=l0;j<r0;++j){
                        Do(v0); }
                for(int j=r0;j<l1;++j){
                                }
                for(int j=l1;j<r1;++j){
                        Do(v1); }
        }
        else if(l0<=l1&&l1<=r0&&r0<=r1&&1){
                for(int j=l0;j<l1;++j){
                        Do(v0); }
                for(int j=l1;j<r0;++j){
                        Do(v0);Do(v1);  }
                for(int j=r0;j<r1;++j){
                        Do(v1); }
        }
        else if(l0<=l1&&l1<=r1&&r1<=r0&&1){
                for(int j=l0;j<l1;++j){
                        Do(v0); }
                for(int j=l1;j<r1;++j){
                        Do(v0);Do(v1);  }
                for(int j=r1;j<r0;++j){
                        Do(v0); }
        }
        else if(l1<=l0&&l0<=r0&&r0<=r1&&1){
                for(int j=l1;j<l0;++j){
                        Do(v1); }
                for(int j=l0;j<r0;++j){
                        Do(v0);Do(v1);  }
                for(int j=r0;j<r1;++j){
                        Do(v1); }
        }
        else if(l1<=l0&&l0<=r1&&r1<=r0&&1){
                for(int j=l1;j<l0;++j){
                        Do(v1); }
                for(int j=l0;j<r1;++j){
                        Do(v0);Do(v1);  }
                for(int j=r1;j<r0;++j){
                        Do(v0); }
        }
        else if(l1<=r1&&r1<=l0&&l0<=r0&&1){
                for(int j=l1;j<r1;++j){
                        Do(v1); }
                for(int j=r1;j<l0;++j){
                                }
                for(int j=l0;j<r0;++j){
                        Do(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("int v2=v[i+2], l2=l[i+2], r2=r[i+2]+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)
        {
            printf("\tfor(int j=%c%d;",a&(1<<p[i])?'r':'l',p[i]);
            a ^= (1<<p[i]);
            printf("j<%c%d;++j){\n\t\t",a&(1<<p[i+1])?'r':'l',p[i+1]);
            Loop(j,0,2)
                if(a&(1<<j))
                    printf("Do(v%d);", j);
            printf("\t}\n");
        }
        printf("}\n");
    }while(next_permutation(p, p+4));
}*/

Compilation message

candies.cpp:108:5: warning: "/*" within comment [-Wcomment]
  108 |     /*vec c(200000, 1e9);
      |

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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 440 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3036 ms 16192 KB Output is correct
2 Correct 2845 ms 14916 KB Output is correct
3 Correct 2832 ms 14784 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 101 ms 10312 KB Output is correct
3 Correct 89 ms 7596 KB Output is correct
4 Correct 2930 ms 17156 KB Output is correct
5 Correct 2806 ms 14464 KB Output is correct
6 Correct 2779 ms 14400 KB Output is correct
7 Correct 2789 ms 14464 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 9896 KB Output is correct
4 Correct 122 ms 5536 KB Output is correct
5 Execution timed out 5050 ms 12740 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 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 440 KB Output is correct
6 Correct 3036 ms 16192 KB Output is correct
7 Correct 2845 ms 14916 KB Output is correct
8 Correct 2832 ms 14784 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 101 ms 10312 KB Output is correct
11 Correct 89 ms 7596 KB Output is correct
12 Correct 2930 ms 17156 KB Output is correct
13 Correct 2806 ms 14464 KB Output is correct
14 Correct 2779 ms 14400 KB Output is correct
15 Correct 2789 ms 14464 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 9896 KB Output is correct
19 Correct 122 ms 5536 KB Output is correct
20 Execution timed out 5050 ms 12740 KB Time limit exceeded
21 Halted 0 ms 0 KB -