oj.uz

Submission #527370

# Submission time Handle Problem Language Result Execution time Memory
527370 2022-02-17T09:56:31 Z stefantaga Handcrafted Gift (IOI20_gift) C++14
55 / 100
 144 ms 24136 KB 
#include <bits/stdc++.h>
#include "gift.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <string>
using namespace std;
int smen[500005];
int ok[500005];
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    int i;
    for (i=0;i<r;i++)
    {
        a[i]++;b[i]++;
    }
    for (i=0;i<r;i++)
    {
        if (x[i]==1)
        {
            smen[a[i]]++;
            smen[b[i]+1]--;
        }
    }
    for (i=1;i<=n;i++)
    {
        smen[i]=smen[i]+smen[i-1];
        if (smen[i]!=0)
        {
            ok[i]=ok[i-1]+1;
        }
    }
    for (i=0;i<r;i++)
    {
        if (x[i]==1)
        {
            continue;
        }
        if (ok[b[i]]-ok[a[i]-1]==b[i]-a[i]+1)
        {
            return 0;
        }
    }
    string s;
    s.resize(n);
    s[0]='R';
    for (i=1;i<n;i++)
    {
        if (ok[i+1]<=1)
        {
            if (s[i-1]=='R')
            {
                s[i]='B';
            }
            else
            {
                s[i]='R';
            }
        }
        else
        {
            s[i]=s[i-1];
        }
    }
    craft(s);
    return 1;
}
#ifdef HOME
static int n, r;
static std::vector<int> a, b, x;
static std::string s;
static int possible = 0;
static int called = 0;
void craft(std::string &_s)
{
    assert(!called);
    s = _s;
    assert((int) s.size() == n);
    for (int i = 0; i < n; i++) {
        assert(s[i] == 'R' || s[i] == 'B');
    }
    called = 1;
}

int main()
{
    assert(scanf("%d %d", &n, &r) == 2);
    a.resize(r);
    b.resize(r);
    x.resize(r);
    for (int i = 0; i < r; i++) {
        assert(scanf("%d %d %d", &a[i], &b[i], &x[i]) == 3);
    }

    fclose(stdin);

    possible = construct(n, r, a, b, x);

    assert(possible == 0 || possible == 1);

    printf("%d\n", possible);

    if (possible == 1) {
        printf("%s\n", s.c_str());
    } else {
        assert(!called);
    }

}
#endif // HOME

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 134 ms 22812 KB Output is correct
6 Correct 128 ms 22828 KB Output is correct
7 Correct 128 ms 24136 KB Output is correct
8 Correct 138 ms 24092 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 660 KB Output is correct
4 Correct 132 ms 22552 KB Output is correct
5 Correct 137 ms 22548 KB Output is correct
6 Incorrect 144 ms 22616 KB Possible does not match answer file
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 134 ms 22812 KB Output is correct
6 Correct 128 ms 22828 KB Output is correct
7 Correct 128 ms 24136 KB Output is correct
8 Correct 138 ms 24092 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 3 ms 660 KB Output is correct
12 Correct 132 ms 22552 KB Output is correct
13 Correct 137 ms 22548 KB Output is correct
14 Incorrect 144 ms 22616 KB Possible does not match answer file
15 Halted 0 ms 0 KB -