oj.uz

답안 #574709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574709 2022-06-09T09:45:20 Z KrisjanisP Handcrafted Gift (IOI20_gift) C++14
10 / 100
 225 ms 28716 KB 
#include "gift.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

void compress(vector<ii>& one)
{
    sort(one.begin(),one.end());
    vector<ii> newOne;
    newOne.push_back(one[0]);
    for(ll i=1;i<one.size();i++)
    {
        if(one[i].first<=newOne.back().second)
            newOne.back().second=max(newOne.back().second,one[i].second);
        else
            newOne.push_back(one[i]);
    }
    one = newOne;
}

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    vector<ii> one, two;
    for(ll i=0;i<r;i++)
    {
        if(x[i]==1) one.push_back({a[i],b[i]});
        else two.push_back({a[i],b[i]});
    }
    if(one.size())
        compress(one);
    vector<bool> same(n,false);
    for(ll i=0;i<one.size();i++)
    {
        for(ll j=one[i].first+1;j<=one[i].second;j++)
            same[j]=true;
    }
    vector<ll> vec(n,0);
    vec[0]=0;
    for(ll i=1;i<n;i++)
    {
        if(same[i]) vec[i]=vec[i-1];
        else vec[i]=1-vec[i-1];
    }
    vector<ll> ps(n,0);
    ps[0]=vec[0]; for(ll i=1;i<n;i++) ps[i]=ps[i-1]+vec[i];
    bool found = false;
    for(ll i=0;i<two.size();i++)
    {
        ll sum = ps[two[i].second];
        if(two[i].first) sum-=ps[two[i].first];
        if(sum==0||sum==(two[i].second-two[i].first+1))
        {
            found=true;
            break;
        }
    }
    if(found) return 0; // answer doesn't exist

    std::string res(n, 'R');
    for(ll i=0;i<n;i++)
        if(vec[i]) res[i]='B';
    
    craft(res);
    return 1;
}

Compilation message

gift.cpp: In function 'void compress(std::vector<std::pair<long long int, long long int> >&)':
gift.cpp:12:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(ll i=1;i<one.size();i++)
      |                ~^~~~~~~~~~~
gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:32:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(ll i=0;i<one.size();i++)
      |                ~^~~~~~~~~~~
gift.cpp:47:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(ll i=0;i<two.size();i++)
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 924 KB Output is correct
5 Correct 225 ms 28660 KB Output is correct
6 Correct 184 ms 28660 KB Output is correct
7 Correct 217 ms 28664 KB Output is correct
8 Correct 183 ms 28716 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 4 ms 852 KB Possible does not match answer file
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Possible does not match answer file
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 1 ms 340 KB Possible does not match answer file
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 924 KB Output is correct
5 Correct 225 ms 28660 KB Output is correct
6 Correct 184 ms 28660 KB Output is correct
7 Correct 217 ms 28664 KB Output is correct
8 Correct 183 ms 28716 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 4 ms 852 KB Possible does not match answer file
12 Halted 0 ms 0 KB -