제출 #1121900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121900		_callmelucian	Alternating Current (BOI18_alternating)	C++14	19 / 100	34 ms	3312 KiB

alternating

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
pii special[mn];
int state[mn];

bool getCur (int mask, int pos) {
    return mask >> pos & 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> orda, ordb, pickSpec;
    vector<tpl> regular;

    /// read wires info
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if (a <= b) regular.emplace_back(a, b, i);
        else {
            special[i] = {a, b};
            orda.push_back(i);
            ordb.push_back(i);
        }
    }
    sort(all(orda), [&] (int a, int b) { return special[a].first < special[b].first; });
    sort(all(ordb), [&] (int a, int b) { return special[a].second > special[b].second; });

    /// only pick candidates that has the chance to contribute to the answer
    for (int i = 0; i < 4 && i < orda.size(); i++) pickSpec.push_back(orda[i]);
    for (int i = 0; i < 4 && i < ordb.size(); i++) pickSpec.push_back(ordb[i]);
    sort(all(pickSpec)), filter(pickSpec);

    /// sort regular segments
    sort(all(regular), [&] (tpl a, tpl b) {
         int a0, a1, a2, b0, b1, b2; tie(a0, a1, a2) = a, tie(b0, b1, b2) = b;
         if (a1 == b1) return (a0 == b0 ? a2 < b2 : a0 < b0);
         return a1 < b1;
    });

//    for (auto [a, b, c] : regular) {
//        cout << a << " " << b << " " << c << endl;
//    }

    /// find valid answer
    for (int mask = 0; mask < (1 << pickSpec.size()); mask++) {
        // calculate contribute of special segments
        int si = 0, sj = 0, ti = n + 1, tj = n + 1;
        for (int i = 0; i < pickSpec.size(); i++) {
            int a, b; tie(a, b) = special[pickSpec[i]];
//            cout << "spec " << pickSpec[i] << " " << a << " " << b << "\n";
            if (getCur(mask, i)) {
                state[pickSpec[i]] = 1;
                si = max(si, b), ti = min(ti, a);
            }
            else {
                state[pickSpec[i]] = 0;
                sj = max(sj, b), tj = min(tj, a);
            }
        }

//        cout << "try " << si << " " << sj << " -> " << ti << " " << tj << "\n";

        // calculate contribute of regular segments
        for (tpl item : regular) {
            int a, b, idx; tie(a, b, idx) = item;
            if (a <= min(si, sj) + 1 && si < ti - 1 && sj < tj - 1) {
                if (si < sj) si = max(si, b), state[idx] = 1;
                else sj = max(sj, b), state[idx] = 0;
            }
            else if (a <= si + 1 && si < ti - 1) si = max(si, b), state[idx] = 1;
            else if (a <= sj + 1 && sj < tj - 1) sj = max(sj, b), state[idx] = 0;
        }

        // check answers
        if (si >= ti - 1 && sj >= tj - 1) {
            for (int i = 0; i < m; i++) cout << state[i];
            return 0;
        }
    }
    cout << "impossible";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

alternating.cpp: In function 'int main()':
alternating.cpp:44:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < 4 && i < orda.size(); i++) pickSpec.push_back(orda[i]);
      |                              ~~^~~~~~~~~~~~~
alternating.cpp:45:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < 4 && i < ordb.size(); i++) pickSpec.push_back(ordb[i]);
      |                              ~~^~~~~~~~~~~~~
alternating.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < pickSpec.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26