Ideone.com

fork download

copy

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }
 
/* Author: Van Hanh Pham */
 
class DisjointSet {
private:
    vector<int> lab;
 
public:
    DisjointSet(int n = 0) {
        lab.assign(n + 7, -1);
    }
 
    int find(int x) {
        return lab[x] < 0 ? x : lab[x] = find(lab[x]);
    }
 
    bool join(int u, int v) {
        int x = find(u), y = find(v);
        if (x == y) return false;
 
        if (lab[x] > lab[y]) swap(x, y);
        lab[x] += lab[y];
        lab[y] = x;
        return true;
    }
 
    int getSize(int u) {
        return -lab[find(u)];
    }
};
 
/** END OF TEMPLATE. DRINK A CUP OF TIGERSUGAR BEFORE READING MY CODE. **/
 
struct Clue {
    int u, v, sign;
 
    Clue(int _u = 0, int _v = 0, char _sign = 0) {
        u = _u; v = _v;
        sign = _sign == '=' ? 0 : (_sign == '<' ? -1 : 1);
    }
};
 
#define MAX_SIZE   300300
#define MAX_CLUE   500500
#define LOG   20
 
int numValue, numClue, numZero, numOne;
Clue clues[MAX_CLUE];
 
void init(void) {
    scanf("%d%d%d", &numValue, &numClue, &numZero);
    numOne = numValue - numZero;
 
    FOR(i, 1, numClue) {
        char s[5];
        int u, v;
        scanf("%d%s%d", &u, s, &v);
        clues[i] = Clue(u, v, s[0]);
    }
}
 
int numCompBySize[MAX_SIZE];
int buildComponent(int t) {
    DisjointSet dsu(numValue + 2);
    int zeroComp = numValue + 1;
    int oneComp = numValue + 2;
 
    FOR(i, 1, t) {
        int u = clues[i].u, v = clues[i].v;
        if (clues[i].sign == 0) dsu.join(u, v);
        else {
            if (clues[i].sign > 0) swap(u, v);
            dsu.join(zeroComp, u);
            dsu.join(oneComp, v);
        }
    }
 
    int zeroRoot = dsu.find(zeroComp);
    int oneRoot = dsu.find(oneComp);
 
    memset(numCompBySize, 0, (numValue + 1) * sizeof (int));
    FOR(i, 1, numValue) if (i != zeroRoot && i != oneRoot && dsu.find(i) == i)
        numCompBySize[dsu.getSize(i)]++;
 
    return numZero - dsu.getSize(zeroComp) + 1;
    return min(numZero - dsu.getSize(zeroComp), numOne - dsu.getSize(oneComp)) + 1;
}
 
#define Bitset bitset<BIT_SET_SIZE>
template<int BIT_SET_SIZE>
    string printBitset(const Bitset &bs, int needZero) {
        stringstream stream;
        stream << "(";
        REP(i, needZero + 1) if (bs[i]) stream << i << ", ";
        stream << ")";
        return stream.str();
    }
 
template<int BIT_SET_SIZE>
    bool checkUnique(int needZero) {
        if (needZero == 0) return true;
        assert(needZero < BIT_SET_SIZE);
 
//        printf("CHECKING UNIQUE %d zeros\n", needZero);
        vector<int> sizes;
        FOR(i, 1, needZero) if (numCompBySize[i] > 0) sizes.push_back(i);
 
        Bitset oneWay, manyWay;
        oneWay[0] = true;
    //    cerr << "oneway: " << printBitset(oneWay, needZero) << endl;
    //    cerr << "manyway: " << printBitset(manyWay, needZero) << endl;
 
        FORE(it, sizes) {
            int compSize = *it;
            int numComp = numCompBySize[compSize];
//            printf("There are %d comps of size %d\n", numComp, compSize);
 
            if (numComp > 1) {
                Bitset combined = (oneWay | manyWay) << compSize;
                manyWay |= manyWay << (numComp * compSize);
                int mask = 1;
                while ((mask << 1) < numComp) {
                    combined = combined | (combined << (mask * compSize));
                    mask <<= 1;
                    if (combined[needZero]) return false;
                }
                manyWay |= combined | (combined << (numComp - 1 - mask) * compSize);
            } else manyWay |= manyWay << (numComp * compSize);
 
            Bitset tmp = oneWay << (compSize * numComp);
            manyWay |= oneWay & tmp;
            oneWay |= tmp;
            oneWay &= ~manyWay;
 
    //        cerr << "oneway: " << printBitset(oneWay, needZero) << endl;
    //        cerr << "manyway: " << printBitset(manyWay, needZero) << endl;
            if (manyWay[needZero]) return false;
        }
 
        assert(oneWay[needZero] || manyWay[needZero]);
        return !manyWay[needZero];
    }
 
bool checkUniqueWithDynamicSize(int needZero) {
    if (needZero < 10) return checkUnique<10>(needZero);
    if (needZero < 20) return checkUnique<20>(needZero);
    if (needZero < 30) return checkUnique<30>(needZero);
    if (needZero < 40) return checkUnique<40>(needZero);
    if (needZero < 50) return checkUnique<50>(needZero);
    if (needZero < 60) return checkUnique<60>(needZero);
    if (needZero < 70) return checkUnique<70>(needZero);
    if (needZero < 80) return checkUnique<80>(needZero);
    if (needZero < 90) return checkUnique<90>(needZero);
    if (needZero < 100) return checkUnique<100>(needZero);
    if (needZero < 200) return checkUnique<200>(needZero);
    if (needZero < 300) return checkUnique<300>(needZero);
    if (needZero < 400) return checkUnique<400>(needZero);
    if (needZero < 500) return checkUnique<500>(needZero);
    if (needZero < 600) return checkUnique<600>(needZero);
    if (needZero < 700) return checkUnique<700>(needZero);
    if (needZero < 800) return checkUnique<800>(needZero);
    if (needZero < 900) return checkUnique<900>(needZero);
    if (needZero < 1000) return checkUnique<1000>(needZero);
    if (needZero < 2000) return checkUnique<2000>(needZero);
    if (needZero < 3000) return checkUnique<3000>(needZero);
    if (needZero < 4000) return checkUnique<4000>(needZero);
    if (needZero < 5000) return checkUnique<5000>(needZero);
    if (needZero < 6000) return checkUnique<6000>(needZero);
    if (needZero < 7000) return checkUnique<7000>(needZero);
    if (needZero < 8000) return checkUnique<8000>(needZero);
    if (needZero < 9000) return checkUnique<9000>(needZero);
    if (needZero < 10000) return checkUnique<10000>(needZero);
    if (needZero < 20000) return checkUnique<20000>(needZero);
    if (needZero < 30000) return checkUnique<30000>(needZero);
    if (needZero < 40000) return checkUnique<40000>(needZero);
    if (needZero < 50000) return checkUnique<50000>(needZero);
    if (needZero < 60000) return checkUnique<60000>(needZero);
    if (needZero < 70000) return checkUnique<70000>(needZero);
    if (needZero < 80000) return checkUnique<80000>(needZero);
    if (needZero < 90000) return checkUnique<90000>(needZero);
    if (needZero < 100000) return checkUnique<100000>(needZero);
    if (needZero < 200000) return checkUnique<200000>(needZero);
    if (needZero < 300000) return checkUnique<300000>(needZero);
    if (needZero < 400000) return checkUnique<400000>(needZero);
    if (needZero < 500000) return checkUnique<500000>(needZero);
    if (needZero < 600000) return checkUnique<600000>(needZero);
    if (needZero < 700000) return checkUnique<700000>(needZero);
    if (needZero < 800000) return checkUnique<800000>(needZero);
    if (needZero < 900000) return checkUnique<900000>(needZero);
    assert(false);
}
 
bool ok(int t) {
//    printf("CHECKING %d\n", t);
    int needZero = buildComponent(t);
    return checkUniqueWithDynamicSize(needZero);
}
 
int process(void) {
    if (numZero == 0 || numZero == numValue) return 0;
    if (numClue == 0 || !ok(numClue)) return -1;
 
    int L = 1, R = numClue;
 
    while (true) {
        if (L == R) return L;
        if (R - L == 1) return ok(L) ? L : R;
        int M = (L + R) >> 1;
        if (ok(M)) R = M; else L = M + 1;
    }
 
}
 
int main(void) {
//    freopen("tests/huge_3.in", "r", stdin);
    int numTest; scanf("%d", &numTest);
    REP(love, numTest) {
        init();
        int result = process();
        printf("%d\n", result);
//        fprintf(stderr, "%d out of %d (%.2lf%%) (#zero = %d, #clue = %d)\n",
//                        result, numValue, 100.0 * result / numValue, numZero, numClue);
    }
    return 0;
}
 
/*** BUBBLE TEA IS GREAT. MY CODE IS AMAZING :D ***/

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBGT1IoaSwgYSwgYikgZm9yIChpbnQgaSA9IChhKSwgX2IgPSAoYik7IGkgPD0gX2I7IGkrKykKI2RlZmluZSBGT1JEKGksIGIsIGEpIGZvciAoaW50IGkgPSAoYiksIF9hID0gKGEpOyBpID49IF9hOyBpLS0pCiNkZWZpbmUgUkVQKGksIG4pIGZvciAoaW50IGkgPSAwLCBfbiA9IChuKTsgaSA8IF9uOyBpKyspCiNkZWZpbmUgRk9SRShpLCB2KSBmb3IgKF9fdHlwZW9mKCh2KS5iZWdpbigpKSBpID0gKHYpLmJlZ2luKCk7IGkgIT0gKHYpLmVuZCgpOyBpKyspCiNkZWZpbmUgQUxMKHYpICh2KS5iZWdpbigpLCAodikuZW5kKCkKI2RlZmluZSBJU19JTkYoeCkgICAoc3RkOjppc2luZih4KSkKI2RlZmluZSBJU19OQU4oeCkgICAoc3RkOjppc25hbih4KSkKI2RlZmluZSBmaSAgIGZpcnN0CiNkZWZpbmUgc2UgICBzZWNvbmQKI2RlZmluZSBNQVNLKGkpICgxTEwgPDwgKGkpKQojZGVmaW5lIEJJVCh4LCBpKSAoKCh4KSA+PiAoaSkpICYgMSkKI2RlZmluZSBkaXYgICBfX19kaXYKI2RlZmluZSBuZXh0ICAgX19fbmV4dAojZGVmaW5lIHByZXYgICBfX19wcmV2CiNkZWZpbmUgbGVmdCAgIF9fX2xlZnQKI2RlZmluZSByaWdodCAgIF9fX3JpZ2h0CiNkZWZpbmUgX19idWlsdGluX3BvcGNvdW50IF9fYnVpbHRpbl9wb3Bjb3VudGxsCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnRlbXBsYXRlPGNsYXNzIFgsIGNsYXNzIFk+CiAgICBib29sIG1pbmltaXplKFggJngsIGNvbnN0IFkgJnkpIHsKICAgICAgICBYIGVwcyA9IDFlLTk7CiAgICAgICAgaWYgKHggPiB5ICsgZXBzKSB7CiAgICAgICAgICAgIHggPSB5OwogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICB9IGVsc2UgcmV0dXJuIGZhbHNlOwogICAgfQp0ZW1wbGF0ZTxjbGFzcyBYLCBjbGFzcyBZPgogICAgYm9vbCBtYXhpbWl6ZShYICZ4LCBjb25zdCBZICZ5KSB7CiAgICAgICAgWCBlcHMgPSAxZS05OwogICAgICAgIGlmICh4ICsgZXBzIDwgeSkgewogICAgICAgICAgICB4ID0geTsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfSBlbHNlIHJldHVybiBmYWxzZTsKICAgIH0KdGVtcGxhdGU8Y2xhc3MgVD4KICAgIFQgQWJzKGNvbnN0IFQgJngpIHsKICAgICAgICByZXR1cm4gKHggPCAwID8gLXggOiB4KTsKICAgIH0KCi8qIEF1dGhvcjogVmFuIEhhbmggUGhhbSAqLwoKY2xhc3MgRGlzam9pbnRTZXQgewpwcml2YXRlOgogICAgdmVjdG9yPGludD4gbGFiOwoKcHVibGljOgogICAgRGlzam9pbnRTZXQoaW50IG4gPSAwKSB7CiAgICAgICAgbGFiLmFzc2lnbihuICsgNywgLTEpOwogICAgfQoKICAgIGludCBmaW5kKGludCB4KSB7CiAgICAgICAgcmV0dXJuIGxhYlt4XSA8IDAgPyB4IDogbGFiW3hdID0gZmluZChsYWJbeF0pOwogICAgfQoKICAgIGJvb2wgam9pbihpbnQgdSwgaW50IHYpIHsKICAgICAgICBpbnQgeCA9IGZpbmQodSksIHkgPSBmaW5kKHYpOwogICAgICAgIGlmICh4ID09IHkpIHJldHVybiBmYWxzZTsKCiAgICAgICAgaWYgKGxhYlt4XSA+IGxhYlt5XSkgc3dhcCh4LCB5KTsKICAgICAgICBsYWJbeF0gKz0gbGFiW3ldOwogICAgICAgIGxhYlt5XSA9IHg7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CgogICAgaW50IGdldFNpemUoaW50IHUpIHsKICAgICAgICByZXR1cm4gLWxhYltmaW5kKHUpXTsKICAgIH0KfTsKCi8qKiBFTkQgT0YgVEVNUExBVEUuIERSSU5LIEEgQ1VQIE9GIFRJR0VSU1VHQVIgQkVGT1JFIFJFQURJTkcgTVkgQ09ERS4gKiovCgpzdHJ1Y3QgQ2x1ZSB7CiAgICBpbnQgdSwgdiwgc2lnbjsKCiAgICBDbHVlKGludCBfdSA9IDAsIGludCBfdiA9IDAsIGNoYXIgX3NpZ24gPSAwKSB7CiAgICAgICAgdSA9IF91OyB2ID0gX3Y7CiAgICAgICAgc2lnbiA9IF9zaWduID09ICc9JyA/IDAgOiAoX3NpZ24gPT0gJzwnID8gLTEgOiAxKTsKICAgIH0KfTsKCiNkZWZpbmUgTUFYX1NJWkUgICAzMDAzMDAKI2RlZmluZSBNQVhfQ0xVRSAgIDUwMDUwMAojZGVmaW5lIExPRyAgIDIwCgppbnQgbnVtVmFsdWUsIG51bUNsdWUsIG51bVplcm8sIG51bU9uZTsKQ2x1ZSBjbHVlc1tNQVhfQ0xVRV07Cgp2b2lkIGluaXQodm9pZCkgewogICAgc2NhbmYoIiVkJWQlZCIsICZudW1WYWx1ZSwgJm51bUNsdWUsICZudW1aZXJvKTsKICAgIG51bU9uZSA9IG51bVZhbHVlIC0gbnVtWmVybzsKCiAgICBGT1IoaSwgMSwgbnVtQ2x1ZSkgewogICAgICAgIGNoYXIgc1s1XTsKICAgICAgICBpbnQgdSwgdjsKICAgICAgICBzY2FuZigiJWQlcyVkIiwgJnUsIHMsICZ2KTsKICAgICAgICBjbHVlc1tpXSA9IENsdWUodSwgdiwgc1swXSk7CiAgICB9Cn0KCmludCBudW1Db21wQnlTaXplW01BWF9TSVpFXTsKaW50IGJ1aWxkQ29tcG9uZW50KGludCB0KSB7CiAgICBEaXNqb2ludFNldCBkc3UobnVtVmFsdWUgKyAyKTsKICAgIGludCB6ZXJvQ29tcCA9IG51bVZhbHVlICsgMTsKICAgIGludCBvbmVDb21wID0gbnVtVmFsdWUgKyAyOwoKICAgIEZPUihpLCAxLCB0KSB7CiAgICAgICAgaW50IHUgPSBjbHVlc1tpXS51LCB2ID0gY2x1ZXNbaV0udjsKICAgICAgICBpZiAoY2x1ZXNbaV0uc2lnbiA9PSAwKSBkc3Uuam9pbih1LCB2KTsKICAgICAgICBlbHNlIHsKICAgICAgICAgICAgaWYgKGNsdWVzW2ldLnNpZ24gPiAwKSBzd2FwKHUsIHYpOwogICAgICAgICAgICBkc3Uuam9pbih6ZXJvQ29tcCwgdSk7CiAgICAgICAgICAgIGRzdS5qb2luKG9uZUNvbXAsIHYpOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgemVyb1Jvb3QgPSBkc3UuZmluZCh6ZXJvQ29tcCk7CiAgICBpbnQgb25lUm9vdCA9IGRzdS5maW5kKG9uZUNvbXApOwoKICAgIG1lbXNldChudW1Db21wQnlTaXplLCAwLCAobnVtVmFsdWUgKyAxKSAqIHNpemVvZiAoaW50KSk7CiAgICBGT1IoaSwgMSwgbnVtVmFsdWUpIGlmIChpICE9IHplcm9Sb290ICYmIGkgIT0gb25lUm9vdCAmJiBkc3UuZmluZChpKSA9PSBpKQogICAgICAgIG51bUNvbXBCeVNpemVbZHN1LmdldFNpemUoaSldKys7CgogICAgcmV0dXJuIG51bVplcm8gLSBkc3UuZ2V0U2l6ZSh6ZXJvQ29tcCkgKyAxOwogICAgcmV0dXJuIG1pbihudW1aZXJvIC0gZHN1LmdldFNpemUoemVyb0NvbXApLCBudW1PbmUgLSBkc3UuZ2V0U2l6ZShvbmVDb21wKSkgKyAxOwp9CgojZGVmaW5lIEJpdHNldCBiaXRzZXQ8QklUX1NFVF9TSVpFPgp0ZW1wbGF0ZTxpbnQgQklUX1NFVF9TSVpFPgogICAgc3RyaW5nIHByaW50Qml0c2V0KGNvbnN0IEJpdHNldCAmYnMsIGludCBuZWVkWmVybykgewogICAgICAgIHN0cmluZ3N0cmVhbSBzdHJlYW07CiAgICAgICAgc3RyZWFtIDw8ICIoIjsKICAgICAgICBSRVAoaSwgbmVlZFplcm8gKyAxKSBpZiAoYnNbaV0pIHN0cmVhbSA8PCBpIDw8ICIsICI7CiAgICAgICAgc3RyZWFtIDw8ICIpIjsKICAgICAgICByZXR1cm4gc3RyZWFtLnN0cigpOwogICAgfQoKdGVtcGxhdGU8aW50IEJJVF9TRVRfU0laRT4KICAgIGJvb2wgY2hlY2tVbmlxdWUoaW50IG5lZWRaZXJvKSB7CiAgICAgICAgaWYgKG5lZWRaZXJvID09IDApIHJldHVybiB0cnVlOwogICAgICAgIGFzc2VydChuZWVkWmVybyA8IEJJVF9TRVRfU0laRSk7CgovLyAgICAgICAgcHJpbnRmKCJDSEVDS0lORyBVTklRVUUgJWQgemVyb3NcbiIsIG5lZWRaZXJvKTsKICAgICAgICB2ZWN0b3I8aW50PiBzaXplczsKICAgICAgICBGT1IoaSwgMSwgbmVlZFplcm8pIGlmIChudW1Db21wQnlTaXplW2ldID4gMCkgc2l6ZXMucHVzaF9iYWNrKGkpOwoKICAgICAgICBCaXRzZXQgb25lV2F5LCBtYW55V2F5OwogICAgICAgIG9uZVdheVswXSA9IHRydWU7CiAgICAvLyAgICBjZXJyIDw8ICJvbmV3YXk6ICIgPDwgcHJpbnRCaXRzZXQob25lV2F5LCBuZWVkWmVybykgPDwgZW5kbDsKICAgIC8vICAgIGNlcnIgPDwgIm1hbnl3YXk6ICIgPDwgcHJpbnRCaXRzZXQobWFueVdheSwgbmVlZFplcm8pIDw8IGVuZGw7CgogICAgICAgIEZPUkUoaXQsIHNpemVzKSB7CiAgICAgICAgICAgIGludCBjb21wU2l6ZSA9ICppdDsKICAgICAgICAgICAgaW50IG51bUNvbXAgPSBudW1Db21wQnlTaXplW2NvbXBTaXplXTsKLy8gICAgICAgICAgICBwcmludGYoIlRoZXJlIGFyZSAlZCBjb21wcyBvZiBzaXplICVkXG4iLCBudW1Db21wLCBjb21wU2l6ZSk7CgogICAgICAgICAgICBpZiAobnVtQ29tcCA+IDEpIHsKICAgICAgICAgICAgICAgIEJpdHNldCBjb21iaW5lZCA9IChvbmVXYXkgfCBtYW55V2F5KSA8PCBjb21wU2l6ZTsKICAgICAgICAgICAgICAgIG1hbnlXYXkgfD0gbWFueVdheSA8PCAobnVtQ29tcCAqIGNvbXBTaXplKTsKICAgICAgICAgICAgICAgIGludCBtYXNrID0gMTsKICAgICAgICAgICAgICAgIHdoaWxlICgobWFzayA8PCAxKSA8IG51bUNvbXApIHsKICAgICAgICAgICAgICAgICAgICBjb21iaW5lZCA9IGNvbWJpbmVkIHwgKGNvbWJpbmVkIDw8IChtYXNrICogY29tcFNpemUpKTsKICAgICAgICAgICAgICAgICAgICBtYXNrIDw8PSAxOwogICAgICAgICAgICAgICAgICAgIGlmIChjb21iaW5lZFtuZWVkWmVyb10pIHJldHVybiBmYWxzZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIG1hbnlXYXkgfD0gY29tYmluZWQgfCAoY29tYmluZWQgPDwgKG51bUNvbXAgLSAxIC0gbWFzaykgKiBjb21wU2l6ZSk7CiAgICAgICAgICAgIH0gZWxzZSBtYW55V2F5IHw9IG1hbnlXYXkgPDwgKG51bUNvbXAgKiBjb21wU2l6ZSk7CgogICAgICAgICAgICBCaXRzZXQgdG1wID0gb25lV2F5IDw8IChjb21wU2l6ZSAqIG51bUNvbXApOwogICAgICAgICAgICBtYW55V2F5IHw9IG9uZVdheSAmIHRtcDsKICAgICAgICAgICAgb25lV2F5IHw9IHRtcDsKICAgICAgICAgICAgb25lV2F5ICY9IH5tYW55V2F5OwoKICAgIC8vICAgICAgICBjZXJyIDw8ICJvbmV3YXk6ICIgPDwgcHJpbnRCaXRzZXQob25lV2F5LCBuZWVkWmVybykgPDwgZW5kbDsKICAgIC8vICAgICAgICBjZXJyIDw8ICJtYW55d2F5OiAiIDw8IHByaW50Qml0c2V0KG1hbnlXYXksIG5lZWRaZXJvKSA8PCBlbmRsOwogICAgICAgICAgICBpZiAobWFueVdheVtuZWVkWmVyb10pIHJldHVybiBmYWxzZTsKICAgICAgICB9CgogICAgICAgIGFzc2VydChvbmVXYXlbbmVlZFplcm9dIHx8IG1hbnlXYXlbbmVlZFplcm9dKTsKICAgICAgICByZXR1cm4gIW1hbnlXYXlbbmVlZFplcm9dOwogICAgfQoKYm9vbCBjaGVja1VuaXF1ZVdpdGhEeW5hbWljU2l6ZShpbnQgbmVlZFplcm8pIHsKICAgIGlmIChuZWVkWmVybyA8IDEwKSByZXR1cm4gY2hlY2tVbmlxdWU8MTA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDIwKSByZXR1cm4gY2hlY2tVbmlxdWU8MjA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDMwKSByZXR1cm4gY2hlY2tVbmlxdWU8MzA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDQwKSByZXR1cm4gY2hlY2tVbmlxdWU8NDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDUwKSByZXR1cm4gY2hlY2tVbmlxdWU8NTA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDYwKSByZXR1cm4gY2hlY2tVbmlxdWU8NjA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDcwKSByZXR1cm4gY2hlY2tVbmlxdWU8NzA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDgwKSByZXR1cm4gY2hlY2tVbmlxdWU8ODA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDkwKSByZXR1cm4gY2hlY2tVbmlxdWU8OTA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDEwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDEwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgMjAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MjAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCAzMDApIHJldHVybiBjaGVja1VuaXF1ZTwzMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDQwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDQwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgNTAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NTAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA2MDApIHJldHVybiBjaGVja1VuaXF1ZTw2MDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDcwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDcwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgODAwKSByZXR1cm4gY2hlY2tVbmlxdWU8ODAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA5MDApIHJldHVybiBjaGVja1VuaXF1ZTw5MDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDEwMDApIHJldHVybiBjaGVja1VuaXF1ZTwxMDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCAyMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MjAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgMzAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDMwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDQwMDApIHJldHVybiBjaGVja1VuaXF1ZTw0MDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA1MDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NTAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgNjAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDYwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDcwMDApIHJldHVybiBjaGVja1VuaXF1ZTw3MDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA4MDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8ODAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgOTAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDkwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDEwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MTAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDIwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MjAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDMwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MzAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDQwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NDAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDUwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NTAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDYwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NjAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDcwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NzAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDgwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8ODAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDkwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8OTAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDEwMDAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDEwMDAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgMjAwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8MjAwMDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCAzMDAwMDApIHJldHVybiBjaGVja1VuaXF1ZTwzMDAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDQwMDAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDQwMDAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgNTAwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8NTAwMDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA2MDAwMDApIHJldHVybiBjaGVja1VuaXF1ZTw2MDAwMDA+KG5lZWRaZXJvKTsKICAgIGlmIChuZWVkWmVybyA8IDcwMDAwMCkgcmV0dXJuIGNoZWNrVW5pcXVlPDcwMDAwMD4obmVlZFplcm8pOwogICAgaWYgKG5lZWRaZXJvIDwgODAwMDAwKSByZXR1cm4gY2hlY2tVbmlxdWU8ODAwMDAwPihuZWVkWmVybyk7CiAgICBpZiAobmVlZFplcm8gPCA5MDAwMDApIHJldHVybiBjaGVja1VuaXF1ZTw5MDAwMDA+KG5lZWRaZXJvKTsKICAgIGFzc2VydChmYWxzZSk7Cn0KCmJvb2wgb2soaW50IHQpIHsKLy8gICAgcHJpbnRmKCJDSEVDS0lORyAlZFxuIiwgdCk7CiAgICBpbnQgbmVlZFplcm8gPSBidWlsZENvbXBvbmVudCh0KTsKICAgIHJldHVybiBjaGVja1VuaXF1ZVdpdGhEeW5hbWljU2l6ZShuZWVkWmVybyk7Cn0KCmludCBwcm9jZXNzKHZvaWQpIHsKICAgIGlmIChudW1aZXJvID09IDAgfHwgbnVtWmVybyA9PSBudW1WYWx1ZSkgcmV0dXJuIDA7CiAgICBpZiAobnVtQ2x1ZSA9PSAwIHx8ICFvayhudW1DbHVlKSkgcmV0dXJuIC0xOwoKICAgIGludCBMID0gMSwgUiA9IG51bUNsdWU7CgogICAgd2hpbGUgKHRydWUpIHsKICAgICAgICBpZiAoTCA9PSBSKSByZXR1cm4gTDsKICAgICAgICBpZiAoUiAtIEwgPT0gMSkgcmV0dXJuIG9rKEwpID8gTCA6IFI7CiAgICAgICAgaW50IE0gPSAoTCArIFIpID4+IDE7CiAgICAgICAgaWYgKG9rKE0pKSBSID0gTTsgZWxzZSBMID0gTSArIDE7CiAgICB9Cgp9CgppbnQgbWFpbih2b2lkKSB7Ci8vICAgIGZyZW9wZW4oInRlc3RzL2h1Z2VfMy5pbiIsICJyIiwgc3RkaW4pOwogICAgaW50IG51bVRlc3Q7IHNjYW5mKCIlZCIsICZudW1UZXN0KTsKICAgIFJFUChsb3ZlLCBudW1UZXN0KSB7CiAgICAgICAgaW5pdCgpOwogICAgICAgIGludCByZXN1bHQgPSBwcm9jZXNzKCk7CiAgICAgICAgcHJpbnRmKCIlZFxuIiwgcmVzdWx0KTsKLy8gICAgICAgIGZwcmludGYoc3RkZXJyLCAiJWQgb3V0IG9mICVkICglLjJsZiUlKSAoI3plcm8gPSAlZCwgI2NsdWUgPSAlZClcbiIsCi8vICAgICAgICAgICAgICAgICAgICAgICAgcmVzdWx0LCBudW1WYWx1ZSwgMTAwLjAgKiByZXN1bHQgLyBudW1WYWx1ZSwgbnVtWmVybywgbnVtQ2x1ZSk7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKLyoqKiBCVUJCTEUgVEVBIElTIEdSRUFULiBNWSBDT0RFIElTIEFNQVpJTkcgOkQgKioqLw==

Success #stdin #stdout 0.02s 9648KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/j8gq1l

language:

C++ 4.3.2 (gcc-4.3.2)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language