oj.uz

Submission #56290

# Submission time Handle Problem Language Result Execution time Memory
56290 2018-07-11T02:30:35 Z model_code Alternating Current (BOI18_alternating) C++17
100 / 100
 137 ms 12632 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 3 ms 548 KB Output is correct
7 Correct 3 ms 548 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 3 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 3 ms 696 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 696 KB Output is correct
18 Correct 2 ms 696 KB Output is correct
19 Correct 3 ms 696 KB Output is correct
20 Correct 2 ms 696 KB Output is correct
21 Correct 2 ms 696 KB Output is correct
22 Correct 2 ms 696 KB Output is correct
23 Correct 3 ms 696 KB Output is correct
24 Correct 2 ms 696 KB Output is correct
25 Correct 2 ms 696 KB Output is correct
26 Correct 2 ms 696 KB Output is correct
27 Correct 2 ms 696 KB Output is correct
28 Correct 2 ms 696 KB Output is correct
29 Correct 3 ms 696 KB Output is correct
30 Correct 2 ms 696 KB Output is correct
31 Correct 2 ms 696 KB Output is correct
32 Correct 3 ms 748 KB Output is correct
33 Correct 2 ms 760 KB Output is correct
34 Correct 2 ms 760 KB Output is correct
35 Correct 3 ms 760 KB Output is correct
36 Correct 3 ms 760 KB Output is correct
37 Correct 2 ms 760 KB Output is correct
38 Correct 3 ms 760 KB Output is correct
39 Correct 2 ms 760 KB Output is correct
40 Correct 2 ms 760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 760 KB Output is correct
20 Correct 2 ms 760 KB Output is correct
21 Correct 2 ms 760 KB Output is correct
22 Correct 2 ms 760 KB Output is correct
23 Correct 2 ms 760 KB Output is correct
24 Correct 2 ms 760 KB Output is correct
25 Correct 2 ms 760 KB Output is correct
26 Correct 2 ms 760 KB Output is correct
27 Correct 3 ms 760 KB Output is correct
28 Correct 2 ms 760 KB Output is correct
29 Correct 2 ms 760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 764 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 3 ms 764 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 3 ms 764 KB Output is correct
8 Correct 2 ms 764 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 1 ms 764 KB Output is correct
11 Correct 4 ms 764 KB Output is correct
12 Correct 3 ms 764 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 2 ms 764 KB Output is correct
15 Correct 3 ms 764 KB Output is correct
16 Correct 3 ms 764 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 4 ms 764 KB Output is correct
19 Correct 3 ms 764 KB Output is correct
20 Correct 3 ms 764 KB Output is correct
21 Correct 3 ms 764 KB Output is correct
22 Correct 3 ms 764 KB Output is correct
23 Correct 3 ms 764 KB Output is correct
24 Correct 2 ms 764 KB Output is correct
25 Correct 2 ms 764 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 2 ms 764 KB Output is correct
28 Correct 3 ms 764 KB Output is correct
29 Correct 3 ms 764 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 12404 KB Output is correct
2 Correct 2 ms 12404 KB Output is correct
3 Correct 46 ms 12404 KB Output is correct
4 Correct 51 ms 12404 KB Output is correct
5 Correct 115 ms 12404 KB Output is correct
6 Correct 98 ms 12404 KB Output is correct
7 Correct 93 ms 12404 KB Output is correct
8 Correct 4 ms 12404 KB Output is correct
9 Correct 3 ms 12404 KB Output is correct
10 Correct 94 ms 12404 KB Output is correct
11 Correct 70 ms 12404 KB Output is correct
12 Correct 135 ms 12404 KB Output is correct
13 Correct 7 ms 12404 KB Output is correct
14 Correct 2 ms 12404 KB Output is correct
15 Correct 126 ms 12632 KB Output is correct
16 Correct 34 ms 12632 KB Output is correct
17 Correct 108 ms 12632 KB Output is correct
18 Correct 137 ms 12632 KB Output is correct
19 Correct 6 ms 12632 KB Output is correct
20 Correct 80 ms 12632 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 58 ms 12632 KB Output is correct
3 Correct 38 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 6 ms 12632 KB Output is correct
6 Correct 31 ms 12632 KB Output is correct
7 Correct 33 ms 12632 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 13 ms 12632 KB Output is correct
10 Correct 88 ms 12632 KB Output is correct
11 Correct 37 ms 12632 KB Output is correct
12 Correct 48 ms 12632 KB Output is correct
13 Correct 2 ms 12632 KB Output is correct
14 Correct 3 ms 12632 KB Output is correct
15 Correct 113 ms 12632 KB Output is correct
16 Correct 26 ms 12632 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 40 ms 12632 KB Output is correct
19 Correct 57 ms 12632 KB Output is correct
20 Correct 3 ms 12632 KB Output is correct