Submission #300850

#	Time	Username	Problem	Language	Result	Execution time	Memory
300850		whaleee	Handcrafted Gift (IOI20_gift)	C++14	25 / 100	268 ms	17252 KiB

gift

#include <bits/stdc++.h>
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

#include "gift.h"

int construct(int n, int r, vi a, vi b, vi x) {
    string ans(n,'?');
    vpi one_color;
    vpi two_color;

    forn(i,r) {
        if (x[i] == 1) {
            one_color.pb(mp(a[i],b[i]));
        }
        else {
            two_color.pb(mp(a[i],b[i]));
            if (a[i] == b[i]) {
                return 0;
            }
        }
    }

    sort(all(one_color));
    sort(all(two_color));

    int i = 0;
    int color = 'R';
    while (i<one_color.size()) {
        int start = one_color[i].fi;
        int end = one_color[i].se;

        while (i+1<one_color.size() && one_color[i+1].fi <= end) {
            end = max(end,one_color[i+1].se);
            i++;
        }
        
        for (int j=start; j<=end; j++) {
            ans[j] = color;
        }
        if (color == 'R') {
            color = 'B';
        }
        else {
            color = 'R';
        }
        i++;
        
    }

    i = 0;
    
    while (i<two_color.size()) {
        int start = two_color[i].fi;
        int end = two_color[i].se;
        
        while (i+1<two_color.size() && two_color[i+1].fi <= end) {
            end = min(end,two_color[i+1].se);
            i++;
        }

        int cnt_any = 0;
        int cnt_op1 = 0;
        int cnt_op2 = 0;
        vi to_fill;
        for (int j=start; j<=end; j++) {
            if (ans[j] == '?') {
                cnt_any++;
                to_fill.pb(j);
            }
            else if (ans[j] == 'R'){
                cnt_op1++;
            }
            else {
                cnt_op2++;
            }
        }

        if (cnt_op1 > 0 && cnt_op2 > 0) {
            for (int pos: to_fill) {
                ans[pos] = 'R';  // any
            }
        }//ok}
        else if (cnt_any > 0 && cnt_op1 == 0 && cnt_op2 > 0) {
            for (int pos: to_fill) {
                ans[pos] = 'R';
            }
        }
        else if (cnt_any > 0 && cnt_op2 == 0 && cnt_op1 > 0) {
            for (int pos: to_fill) {
                ans[pos] = 'B';
            }
        }
        else if (cnt_op1 == end-start + 1 || cnt_op2 == end-start + 1) {
            return 0;
        }
        else if (cnt_any >= 2) {
            // assert(0);
            color = 'R';
            for (int pos: to_fill) {
                ans[pos] = color;
                if (color == 'R') {
                    color = 'B';
                }
                else {
                    color = 'R';
                }
            }
        }
        else {
            assert(0);
            return 0;
        }
        i++;
    }
    forn(i, n) {
        if (ans[i] == '?') {
            ans[i] = 'R';
        }
    }
    craft(ans);
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, vi, vi, vi)':
gift.cpp:51:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (i<one_color.size()) {
      |            ~^~~~~~~~~~~~~~~~~
gift.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while (i+1<one_color.size() && one_color[i+1].fi <= end) {
      |                ~~~^~~~~~~~~~~~~~~~~
gift.cpp:75:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     while (i<two_color.size()) {
      |            ~^~~~~~~~~~~~~~~~~
gift.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while (i+1<two_color.size() && two_color[i+1].fi <= end) {
      |                ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30