Submission #830627

#	Time	Username	Problem	Language	Result	Execution time	Memory
830627		Johann	Alternating Current (BOI18_alternating)	C++14	100 / 100	108 ms	9900 KiB

alternating

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

#define pii pair<int,int>
#define vi vector<int>
#define vb vector<bool>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

struct wire {
    int a, b, idx;
};

struct item {
    int d1, d2;
    int f2f1, f2f2;
};
const item NEUTRAL = { 0, 0, INT_MAX, INT_MAX };
struct SegTree {
    vector<item> arr;
    int size;
    void update(item & self, item & c1, item & c2) {
        if (self.d1 > 0) self.f2f1 = INT_MAX;
        else if (c1.f2f1 != INT_MAX) self.f2f1 = c1.f2f1;
        else self.f2f1 = c2.f2f1;
        if (self.d2 > 0) self.f2f2 = INT_MAX;
        else if (c1.f2f2 != INT_MAX) self.f2f2 = c1.f2f2;
        else self.f2f2 = c2.f2f2;
    }
    void update(item & self, int pos) {
        self.f2f1 = (self.d1 > 0) ? INT_MAX : pos;
        self.f2f2 = (self.d2 > 0) ? INT_MAX : pos;
    }
    void init(int _n) {
        size = 1;
        while (size < _n) size *= 2;
        arr.assign(2 * size, { 0, 0, INT_MAX, INT_MAX });
        for (int i = 0; i < size; ++i) {
            arr[size + i] = { 0 , 0, i, i };
        }
        for (int x = size-1; x > 0; --x) update(arr[x], arr[2 * x], arr[2 * x + 1]);
    }
    item query(int a, int b) {
        if (a < b) {
            return query(a, b, 1, 0, size);
        } else {
            item ans = { 0, 0, INT_MAX, INT_MAX };
            item c1 = query(a, size, 1, 0, size);
            item c2 = query(0, b, 1, 0, size);
            if (c2.f2f1 != INT_MAX) c2.f2f1 += size;
            if (c2.f2f2 != INT_MAX) c2.f2f2 += size;
            update(ans, c1, c2);
            return ans;
        }
    }
    item query(int a, int b, int x, int lx, int rx) {
        if (a <= lx && rx <= b) { return arr[x] = arr[x]; }
        if (b <= lx || rx <= a) { return NEUTRAL; }
        int m = (lx + rx) / 2;
        item ans = { arr[x].d1, arr[x].d2, INT_MAX, INT_MAX };
        item c1 = query(a, b, 2 * x, lx, m);
        item c2 = query(a, b, 2 * x + 1, m, rx);
        update(ans, c1, c2);
        return ans;
    }
    void set(int a, int b, int c) {
        // current \in { +- 1, +- 2 }
        if (a < b) {
            set(a, b, c, 1, 0, size);
        } else {
            set(a, size, c, 1, 0, size);
            set(0, b, c, 1, 0, size);
        }
    }
    void set(int a, int b, int c, int x, int lx, int rx) {
        if (a <= lx && rx <= b) {
            if (abs(c) == 1) { arr[x].d1 += c; }
            else { arr[x].d2 += c / 2; }
            if (rx - lx > 1) update(arr[x], arr[2 * x], arr[2 * x + 1]);
            else update(arr[x], lx);
            return;
        }
        if (b <= lx || rx <= a) { return; }
        int m = (lx + rx) / 2;
        set(a, b, c, 2 * x, lx, m);
        set(a, b, c, 2*x+1, m, rx);
        update(arr[x], arr[2 * x], arr[2 * x + 1]);
    }
};


bool in(wire a, wire b, int N) { // ist a in b?
    int ea = a.b;
    if (a.b <= a.a) ea += N;
    int eb = b.b;
    if (b.b <= b.a) eb += N;
    return (b.a <= a.a && ea <= eb) || (b.a <= a.a + N && ea + N <= eb);
}

int alter(int state) {
    if (abs(state) == 1) return state * 2;
    else return state / 2;
}
void setSeg(SegTree & seg, wire & parent, vector<wire> & children, vi & states, int state) {
    states[parent.idx] = state;
    seg.set(parent.a, parent.b, state);
    state = alter(state);
    for (wire c : children) {
        states[c.idx] = state;
        seg.set(c.a, c.b, state);
    }
}
void coutStates(vi & states) {
    for (int b : states) printf("%d", b-1);
    cout << endl;
}
void alter(SegTree & seg, wire & parent, vector<wire> & children, vi & states) {
    int oldState = states[parent.idx];
    setSeg(seg, parent, children, states, -oldState);
    setSeg(seg, parent, children, states, alter(oldState));
}
void DebugOutput(SegTree & seg, vi & states, int N) {
    for (int j = 0; j < N; ++j) {
        item tmp = seg.query(j, j + 1);
        cout << ((tmp.f2f1 == INT_MAX) ? "-" : to_string(tmp.f2f1));
        cout << "/" << ((tmp.f2f2 == INT_MAX) ? "-" : to_string(tmp.f2f2));
        cout << " ";
    } cout << endl;
    coutStates(states);
    cout << endl;
}


int main() {

    int N, M;
    scanf("%d %d", &N, &M);
    vector<wire> wires(M);
    vi states(M, 0);
    for (int i = 0,a,b; i < M; ++i) {
        scanf("%d %d", &a, &b);
        wires[i] = { --a, b, i };
    }
    sort(wires.begin(), wires.end(), [&](wire & one, wire & two) {
        if (one.a != two.a) return one.a < two.a;
        else {
            int l1 = one.b - one.a; if (l1 <= 0) l1 += N;
            int l2 = two.b - two.a; if (l2 <= 0) l2 += N;
            return l1 > l2;
        }
    });

    // nasty fehler bei 1 N, 1 N ?
    vector<wire> parents;
    vector<vector<wire>> children;
    parents.push_back(wires[0]);
    children.push_back(vector<wire>());
    for (int i = 1; i < M; ++i) {
        if (in(wires[i], parents.back(), N)) {
            children.back().push_back(wires[i]);
        } else {
            parents.push_back(wires[i]);
            children.push_back(vector<wire>());
        }
    }
    reverse(all(parents));
    reverse(all(children));
    while (parents.size() > 1) {
        if (in(parents.back(), parents.front(), N)) {
            children[0].push_back(parents.back());
            for (wire w : children.back()) children[0].push_back(w);
            parents.pop_back();
            children.pop_back();
        } else {
            break;
        }
    }
    reverse(all(parents));
    reverse(all(children));

    SegTree seg;
    seg.init(N);
    for (int i = 0, s; i < sz(parents); ++i) {
        s = (i % 2) + 1;
        setSeg(seg, parents[i], children[i], states, s);
        // DebugOutput(seg, states, N);
    }
    for (int i = 0; i < sz(parents); ++i) {
        item res = seg.query(0, N);
        if (res.f2f1 == INT_MAX && res.f2f2 == INT_MAX) {
            coutStates(states);
            return 0;
        }
        alter(seg, parents[i], children[i], states);
        // DebugOutput(seg, states, N);
    }
    printf("impossible");

}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
alternating.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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