Submission #56290

#	Time	Username	Problem	Language	Result	Execution time	Memory
56290		model_code	Alternating Current (BOI18_alternating)	C++17	100 / 100	137 ms	12632 KiB

alternating

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <cassert>

using namespace std;

int N;

struct Segment {
    int index, sortedIndex;
    int start, length;
    set<Segment*> enclosedSegments;
    bool direction;

    Segment(int index, int start, int length) : 
        index(index),
        start(start), 
        length(length), 
        direction(0) {
    }

    // Check if this segment is completely inside another segment
    bool isSubsetOf(const Segment& other) const {
        int relativeStart = (start - other.start + N) % N;
        return relativeStart + length <= other.length;
    }

    // Set direction of all children in the opposite direction to this node
    void assignChildren() {
        for (Segment* child : enclosedSegments) {
            child->direction = !direction;
        }
    }

    // Set direction of this node and direction of all children in the opposite direction
    void assign(bool newDirection) {
        direction = newDirection;
        assignChildren();
    }
};

// Assign the children of each given segment in the opposite direction to the parent
void assignChildren(vector<Segment>& segments) {
    for (Segment& segment : segments) {
        segment.assignChildren();
    }
}

// Assign the given segments alternating directions, starting from startIndex
// Note that if independentSegments has an odd number of elements then
// independentSegments[startIndex-1] and independentSegments[startIndex] are
// assigned the same direction
void assignAlternating(vector<Segment*>& independentSegments, int startIndex) {
    for (size_t i = 0; i < independentSegments.size(); i++) {
        size_t j = (i + startIndex) % independentSegments.size();
        independentSegments[j]->assign(i%2);
    }
}

// Returns whether the interval between the beginning of the segment with
// index startIndex and the beginning of the segment with index endIndex
// is completely covered in the given direction
bool checkPartialSolution(const vector<Segment>& segments, size_t startIndex, size_t endIndex, bool direction) {
    size_t n = segments.size();
    int hi = segments[startIndex].start;
    size_t length = ((endIndex - startIndex + n - 1) % n) + 1;
    for (size_t i = 0; i < length; i++) {
        size_t j = (i+startIndex) % n;
        if (segments[j].direction != direction) {
            continue;
        }
        int start = segments[j].start;
        if (j < startIndex) {
            start += N;
        }
        if (start > hi) {
            return false;
        }
        int end = start + segments[j].length;
        hi = max(hi, end);
    }
    int start = segments[endIndex].start;
    if (endIndex <= startIndex) {
        start += N;
    }
    return start <= hi;
}

// Returns whether the given solution covers the whole circle
bool checkSolution(const vector<Segment>& segments) {
    for (int direction = 0; direction < 2; direction++) {
        size_t n = segments.size();
        int hi = 0;
        for (size_t i = 0; i < 2*n; i++) {
            size_t j = i%n;
            if (segments[j].direction != direction) {
                continue;
            }
            int start = segments[j].start;
            if (i < n) {
                start -= N;
            }
            if (start > hi) {
                return false;
            }
            int end = start + segments[j].length;
            hi = max(hi, end);
        }
        if (hi < N) {
            return false;
        }
    }
    return true;
}

void printSolution(const vector<Segment>& segments) {
    vector<bool> directions(segments.size());
    for (const Segment& segment : segments) {
        directions[segment.index] = segment.direction;
    }
    for (bool d : directions) {
        cout << d;
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    int M;
    cin >> N >> M;

    vector<Segment> segments;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        segments.emplace_back(i, a-1, ((b-a+N)%N)+1);
    }

    sort(segments.begin(), segments.end(), [](const Segment& a, const Segment& b) -> bool {
        if (a.start == b.start) {
            return a.length > b.length;
        }
        return a.start < b.start;
    });

    for (int i = 0; i < M; i++) {
        segments[i].sortedIndex = i;
    }
    
    vector<Segment*> independentSegments;
    Segment* lastSegment = &segments[0];
    for (int i = 1; i < 2*M; i++) {
        int j = i%M;
        Segment* currentSegment = &segments[j];
        if (currentSegment != lastSegment && currentSegment->isSubsetOf(*lastSegment)) {
            lastSegment->enclosedSegments.insert(currentSegment);
        }
        else {
            lastSegment = currentSegment;
            if (i >= M) {
                independentSegments.push_back(lastSegment);
            }
        }
    }

    if (independentSegments.size()%2 == 0) {
        assignAlternating(independentSegments, 0);
        assignChildren(segments);
        if (checkSolution(segments)) {
            printSolution(segments);
        }
        else {
            cout << "impossible" << endl;
        }
    }
    else {
        for (size_t i = 0; i < independentSegments.size(); i++) {
            auto A = independentSegments[(i+0)%independentSegments.size()];
            auto B = independentSegments[(i+1)%independentSegments.size()];
            auto C = independentSegments[(i+2)%independentSegments.size()];
            auto D = independentSegments[(i+3)%independentSegments.size()];
            A->assign(0);
            D->assign(0);
            B->assign(1);
            C->assign(1);
            if (checkPartialSolution(segments, A->sortedIndex, D->sortedIndex, 0)) {
                assignAlternating(independentSegments, int((i+2)%independentSegments.size()));
                assignChildren(segments);
                if (checkSolution(segments)) {
                    printSolution(segments);
                }
                else {
                    cout << "impossible" << endl;
                }
                return 0;
            }
        }
        cout << "impossible" << endl;
    }
}

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