Submission #810279

#	Time	Username	Problem	Language	Result	Execution time	Memory
810279		thimote75	Port Facility (JOI17_port_facility)	C++14	10 / 100	860 ms	376 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

using di = pair<int, int>;
using vd = vector<di>;

bool valid (vd pairs) {
    for (int i = 0; i < pairs.size(); i ++) {
        for (int j = 0; j < pairs.size(); j ++) {
            if (i == j) continue ;

            if (pairs[i].first < pairs[j].first
             && pairs[j].first < pairs[i].second
             && pairs[i].second < pairs[j].second)
                return false;
        }
    }

    return true;
}
bool valid (vd pairs, int mask) {
    vd left, right;

    for (int i = 0; i < pairs.size(); i ++) {
        if ((1 << i) & mask) left.push_back(pairs[i]);
        else right.push_back(pairs[i]);
    }

    return valid(left) && valid(right);
}

int main () {
    int N;
    cin >> N;

    vd pairs(N);
    for (int i = 0; i < N; i ++) 
        cin >> pairs[i].first >> pairs[i].second;
    
    int res = 0;
    for (int mask = 0; mask < (1 << N); mask ++)
        if (valid(pairs, mask))
            res ++;
    
    cout << res << endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool valid(vd)':
port_facility.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < pairs.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~
port_facility.cpp:11:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int j = 0; j < pairs.size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~
port_facility.cpp: In function 'bool valid(vd, int)':
port_facility.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < pairs.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22