Submission #952205

#	Time	Username	Problem	Language	Result	Execution time	Memory
952205		arbuzick	Ancient Machine 2 (JOI23_ancient2)	C++17	95 / 100	41 ms	1132 KiB

ancient2

#include "ancient2.h"

#include <bits/stdc++.h>

using namespace std;

bitset<1001> bs[1000];

bool is_answer(int pos, int n) {
    for (int i = 0; i < pos; ++i) {
        for (int j = 0; j < n; ++j) {
            if (bs[i][j]) {
                if (bs[pos][j]) {
                    bs[pos] ^= bs[i];
                }
                break;
            }
        }
    }
    for (int j = 0; j < n; ++j) {
        if (bs[pos][j]) {
            for (int i = 0; i < pos; ++i) {
                if (bs[i][j]) {
                    bs[i] ^= bs[pos];
                }
            }
            return true;
        }
    }
    return false;
}

string get_answer(int n) {
    string ans = "";
    for (int i = 0; i < n; ++i) {
        int pos = -1;
        for (int j = i; j < n; ++j) {
            if (bs[j][i]) {
                pos = j;
                break;
            }
        }
        swap(bs[i], bs[pos]);
        for (int j = 0; j < n; ++j) {
            if (j != i && bs[j][i]) {
                bs[j] ^= bs[i];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        ans += '0' + bs[i][n];
    }
    return ans;
}

string Solve(int n) {
    vector<pair<int, int>> qs = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}, {0, 8}, {0, 9}, {0, 10}, {0, 11}, {0, 12}, {0, 13}, {0, 14}, {0, 15}, {0, 16}, {0, 17}, {0, 18}, {0, 19}, {0, 20}, {0, 21}, {0, 22}, {0, 23}, {0, 24}, {0, 25}, {0, 26}, {0, 27}, {0, 28}, {0, 29}, {0, 30}, {0, 31}, {0, 32}, {0, 33}, {0, 34}, {0, 35}, {0, 36}, {0, 37}, {0, 38}, {0, 39}, {0, 40}, {0, 41}, {0, 42}, {0, 43}, {0, 44}, {0, 45}, {0, 46}, {0, 47}, {0, 48}, {0, 49}, {0, 50}, {0, 51}, {0, 52}, {0, 53}, {0, 54}, {0, 55}, {0, 56}, {0, 57}, {0, 58}, {0, 59}, {0, 60}, {0, 61}, {0, 62}, {1, 1}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1, 10}, {1, 11}, {1, 12}, {1, 13}, {1, 14}, {1, 15}, {1, 16}, {1, 17}, {1, 18}, {1, 19}, {1, 20}, {1, 21}, {1, 22}, {1, 23}, {1, 24}, {1, 25}, {1, 26}, {1, 27}, {1, 28}, {1, 29}, {1, 30}, {1, 31}, {1, 32}, {1, 33}, {1, 34}, {1, 35}, {1, 36}, {1, 37}, {1, 38}, {1, 39}, {1, 40}, {1, 41}, {1, 42}, {1, 43}, {1, 44}, {1, 45}, {1, 46}, {1, 47}, {1, 48}, {1, 49}, {1, 50}, {1, 51}, {1, 52}, {1, 53}, {1, 54}, {1, 55}, {1, 56}, {1, 57}, {1, 58}, {1, 59}, {1, 60}, {1, 61}, {2, 1}, {2, 5}, {2, 7}, {2, 8}, {2, 9}, {2, 10}, {2, 11}, {2, 12}, {2, 13}, {2, 14}, {2, 15}, {2, 16}, {2, 17}, {2, 18}, {2, 19}, {2, 20}, {2, 21}, {2, 22}, {2, 23}, {2, 24}, {2, 25}, {2, 26}, {2, 27}, {2, 28}, {2, 29}, {2, 30}, {2, 31}, {2, 32}, {2, 33}, {2, 34}, {2, 35}, {2, 36}, {2, 37}, {2, 38}, {2, 39}, {2, 40}, {2, 41}, {2, 42}, {2, 43}, {2, 44}, {2, 45}, {2, 46}, {2, 47}, {2, 48}, {2, 49}, {2, 50}, {2, 51}, {2, 52}, {2, 53}, {2, 54}, {2, 55}, {2, 56}, {2, 57}, {2, 58}, {2, 59}, {2, 60}, {2, 61}, {3, 1}, {3, 5}, {3, 7}, {3, 8}, {3, 9}, {3, 10}, {3, 11}, {3, 12}, {3, 13}, {3, 14}, {3, 15}, {3, 16}, {3, 17}, {3, 18}, {3, 19}, {3, 20}, {3, 21}, {3, 22}, {3, 23}, {3, 24}, {3, 25}, {3, 26}, {3, 27}, {3, 28}, {3, 29}, {3, 30}, {3, 31}, {3, 32}, {3, 33}, {3, 34}, {3, 35}, {3, 36}, {3, 37}, {3, 38}, {3, 39}, {3, 40}, {3, 41}, {3, 42}, {3, 43}, {3, 44}, {3, 45}, {3, 46}, {3, 47}, {3, 48}, {3, 49}, {3, 50}, {3, 51}, {3, 52}, {3, 53}, {3, 54}, {3, 55}, {3, 56}, {3, 57}, {3, 58}, {3, 59}, {3, 60}, {4, 1}, {4, 7}, {4, 9}, {4, 11}, {4, 13}, {4, 14}, {4, 15}, {4, 16}, {4, 17}, {4, 18}, {4, 19}, {4, 20}, {4, 21}, {4, 22}, {4, 23}, {4, 24}, {4, 25}, {4, 26}, {4, 27}, {4, 28}, {4, 29}, {4, 30}, {4, 31}, {4, 32}, {4, 33}, {4, 34}, {4, 35}, {4, 36}, {4, 37}, {4, 38}, {4, 39}, {4, 40}, {4, 41}, {4, 42}, {4, 43}, {4, 44}, {4, 45}, {4, 46}, {4, 47}, {4, 48}, {4, 49}, {4, 50}, {4, 51}, {4, 52}, {4, 53}, {4, 54}, {4, 55}, {4, 56}, {4, 57}, {4, 58}, {4, 59}, {4, 60}, {5, 1}, {5, 7}, {5, 9}, {5, 11}, {5, 13}, {5, 14}, {5, 15}, {5, 16}, {5, 17}, {5, 18}, {5, 19}, {5, 20}, {5, 21}, {5, 22}, {5, 23}, {5, 24}, {5, 25}, {5, 26}, {5, 27}, {5, 28}, {5, 29}, {5, 30}, {5, 31}, {5, 32}, {5, 33}, {5, 34}, {5, 35}, {5, 36}, {5, 37}, {5, 38}, {5, 39}, {5, 40}, {5, 41}, {5, 42}, {5, 43}, {5, 44}, {5, 45}, {5, 46}, {5, 47}, {5, 48}, {5, 49}, {5, 50}, {5, 51}, {5, 52}, {5, 53}, {5, 54}, {5, 55}, {5, 56}, {5, 57}, {5, 58}, {5, 59}, {6, 1}, {6, 11}, {6, 13}, {6, 15}, {6, 16}, {6, 17}, {6, 19}, {6, 20}, {6, 21}, {6, 22}, {6, 23}, {6, 24}, {6, 25}, {6, 26}, {6, 27}, {6, 28}, {6, 29}, {6, 30}, {6, 31}, {6, 32}, {6, 33}, {6, 34}, {6, 35}, {6, 36}, {6, 37}, {6, 38}, {6, 39}, {6, 40}, {6, 41}, {6, 42}, {6, 43}, {6, 44}, {6, 45}, {6, 46}, {6, 47}, {6, 48}, {6, 49}, {6, 50}, {6, 51}, {6, 52}, {6, 53}, {6, 54}, {6, 55}, {6, 56}, {6, 57}, {6, 58}, {6, 59}, {7, 1}, {7, 11}, {7, 13}, {7, 15}, {7, 16}, {7, 17}, {7, 19}, {7, 20}, {7, 21}, {7, 22}, {7, 23}, {7, 24}, {7, 25}, {7, 26}, {7, 27}, {7, 28}, {7, 29}, {7, 30}, {7, 31}, {7, 32}, {7, 33}, {7, 34}, {7, 35}, {7, 36}, {7, 37}, {7, 38}, {7, 39}, {7, 40}, {7, 41}, {7, 42}, {7, 43}, {7, 44}, {7, 45}, {7, 46}, {7, 47}, {7, 48}, {7, 49}, {7, 50}, {7, 51}, {7, 52}, {7, 53}, {7, 54}, {7, 55}, {7, 56}, {7, 57}, {7, 58}, {8, 1}, {8, 11}, {8, 13}, {8, 17}, {8, 19}, {8, 21}, {8, 22}, {8, 23}, {8, 25}, {8, 26}, {8, 27}, {8, 28}, {8, 29}, {8, 31}, {8, 32}, {8, 33}, {8, 34}, {8, 35}, {8, 36}, {8, 37}, {8, 38}, {8, 39}, {8, 40}, {8, 41}, {8, 42}, {8, 43}, {8, 44}, {8, 45}, {8, 46}, {8, 47}, {8, 48}, {8, 49}, {8, 50}, {8, 51}, {8, 52}, {8, 53}, {8, 54}, {8, 55}, {8, 56}, {8, 57}, {8, 58}, {9, 1}, {9, 11}, {9, 13}, {9, 17}, {9, 19}, {9, 21}, {9, 22}, {9, 23}, {9, 25}, {9, 26}, {9, 27}, {9, 28}, {9, 29}, {9, 31}, {9, 32}, {9, 33}, {9, 34}, {9, 35}, {9, 36}, {9, 37}, {9, 38}, {9, 39}, {9, 40}, {9, 41}, {9, 42}, {9, 43}, {9, 44}, {9, 45}, {9, 46}, {9, 47}, {9, 48}, {9, 49}, {9, 50}, {9, 51}, {9, 52}, {9, 53}, {9, 54}, {9, 55}, {9, 56}, {9, 57}, {10, 1}, {10, 13}, {10, 17}, {10, 19}, {10, 21}, {10, 23}, {10, 25}, {10, 26}, {10, 27}, {10, 28}, {10, 29}, {10, 31}, {10, 32}, {10, 33}, {10, 34}, {10, 35}, {10, 36}, {10, 37}, {10, 38}, {10, 39}, {10, 40}, {10, 41}, {10, 42}, {10, 43}, {10, 44}, {10, 45}, {10, 46}, {10, 47}, {10, 48}, {10, 49}, {10, 50}, {10, 51}, {10, 52}, {10, 53}, {10, 54}, {10, 55}, {10, 56}, {10, 57}, {11, 1}, {11, 13}, {11, 17}, {11, 19}, {11, 21}, {11, 23}, {11, 25}, {11, 26}, {11, 27}, {11, 28}, {11, 29}, {11, 31}, {11, 32}, {11, 33}, {11, 34}, {11, 35}, {11, 36}, {11, 37}, {11, 38}, {11, 39}, {11, 40}, {11, 41}, {11, 42}, {11, 43}, {11, 44}, {11, 45}, {11, 46}, {11, 47}, {11, 48}, {11, 49}, {11, 50}, {11, 51}, {11, 52}, {11, 53}, {11, 54}, {11, 55}, {11, 56}, {12, 1}, {12, 17}, {12, 19}, {12, 23}, {12, 25}, {12, 27}, {12, 29}, {12, 31}, {12, 32}, {12, 33}, {12, 34}, {12, 35}, {12, 37}, {12, 38}, {12, 39}, {12, 40}, {12, 41}, {12, 43}, {12, 44}, {12, 45}, {12, 46}, {12, 47}, {12, 48}, {12, 49}, {12, 50}, {12, 51}, {12, 52}, {12, 53}, {12, 54}, {12, 55}, {12, 56}, {13, 1}, {13, 17}, {13, 19}, {13, 23}, {13, 25}, {13, 27}, {13, 29}, {13, 31}, {13, 32}, {13, 33}, {13, 34}, {13, 35}, {13, 37}, {13, 38}, {13, 39}, {13, 40}, {13, 41}, {13, 43}, {13, 44}, {13, 45}, {13, 46}, {13, 47}, {13, 48}, {13, 49}, {13, 50}, {13, 51}, {13, 52}, {13, 53}, {13, 54}, {13, 55}, {14, 1}, {14, 17}, {14, 19}, {14, 23}, {14, 25}, {14, 27}, {14, 29}, {14, 31}, {14, 32}, {14, 33}, {14, 34}, {14, 35}, {14, 37}, {14, 38}, {14, 39}, {14, 40}, {14, 41}, {14, 43}, {14, 44}, {14, 45}, {14, 46}, {14, 47}, {14, 48}, {14, 49}, {14, 50}, {14, 51}, {14, 52}, {14, 53}, {14, 54}, {14, 55}, {15, 1}, {15, 17}, {15, 19}, {15, 23}, {15, 25}, {15, 27}, {15, 29}, {15, 31}, {15, 32}, {15, 33}, {15, 34}, {15, 35}, {15, 37}, {15, 38}, {15, 39}, {15, 40}, {15, 41}, {15, 43}, {15, 44}, {15, 45}, {15, 46}, {15, 47}, {15, 48}, {15, 49}, {15, 50}, {15, 51}, {15, 52}, {15, 53}, {15, 54}, {16, 1}, {16, 19}, {16, 23}, {16, 25}, {16, 27}, {16, 29}, {16, 31}, {16, 33}, {16, 35}, {16, 37}, {16, 38}, {16, 39}, {16, 41}, {16, 43}, {16, 44}, {16, 45}, {16, 46}, {16, 47}, {16, 49}, {16, 50}, {16, 51}, {16, 52}, {16, 53}, {16, 54}, {17, 1}, {17, 19}, {17, 23}, {17, 25}, {17, 27}, {17, 29}, {17, 31}, {17, 33}, {17, 35}, {17, 37}, {17, 38}, {17, 39}, {17, 41}, {17, 43}, {17, 44}, {17, 45}, {17, 46}, {17, 47}, {17, 49}, {17, 50}, {17, 51}, {17, 52}, {17, 53}, {18, 1}, {18, 23}, {18, 25}, {18, 29}, {18, 31}, {18, 33}, {18, 35}, {18, 37}, {18, 39}, {18, 41}, {18, 43}, {18, 44}, {18, 45}, {18, 46}, {18, 47}, {18, 49}, {18, 50}, {18, 51}, {18, 52}, {18, 53}, {19, 1}, {19, 23}, {19, 25}, {19, 29}, {19, 31}, {19, 33}, {19, 35}, {19, 37}, {19, 39}, {19, 41}, {19, 43}, {19, 44}, {19, 45}, {19, 46}, {19, 47}, {19, 49}, {19, 50}, {19, 51}, {19, 52}, {20, 1}, {20, 23}, {20, 29}, {20, 31}, {20, 35}, {20, 37}, {20, 39}, {20, 41}, {20, 43}, {20, 45}, {20, 46}, {20, 47}, {20, 49}, {20, 51}, {20, 52}, {21, 1}, {21, 23}, {21, 29}, {21, 31}, {21, 35}, {21, 37}, {21, 39}, {21, 41}, {21, 43}, {21, 45}, {21, 46}, {21, 47}, {21, 49}, {21, 51}, {22, 1}, {22, 29}, {22, 31}, {22, 35}, {22, 37}, {22, 39}, {22, 41}, {22, 43}, {22, 45}, {22, 47}, {22, 49}, {22, 51}, {23, 1}, {23, 29}, {23, 31}, {23, 35}, {23, 37}, {23, 39}, {23, 41}, {23, 43}, {23, 45}, {23, 47}, {23, 49}, {24, 1}, {24, 29}, {24, 31}, {24, 37}, {24, 41}, {24, 43}, {24, 47}, {24, 49}, {25, 1}, {25, 29}, {25, 31}, {25, 37}, {25, 41}, {25, 43}, {25, 47}, {25, 49}, {26, 1}, {26, 29}, {26, 31}, {26, 37}, {26, 41}, {26, 43}, {26, 47}, {26, 49}, {27, 1}, {27, 29}, {27, 31}, {27, 37}, {27, 41}, {27, 43}, {27, 47}, {28, 1}, {28, 31}, {28, 37}, {28, 41}, {28, 43}, {28, 47}, {29, 1}, {29, 31}, {29, 37}, {29, 41}, {29, 43}, {29, 47}, {30, 1}, {30, 37}, {30, 41}, {30, 43}, {30, 47}, {31, 1}, {31, 37}, {31, 41}, {31, 43}, {32, 1}, {32, 37}, {32, 41}, {32, 43}, {33, 1}, {33, 37}, {33, 41}, {33, 43}, {34, 1}, {34, 37}, {34, 41}, {34, 43}, {35, 1}, {35, 37}, {35, 41}, {35, 43}, {36, 1}, {36, 41}, {36, 43}, {37, 1}, {37, 41}, {37, 43}, {38, 1}, {38, 41}, {38, 43}, {39, 1}, {39, 41}, {40, 1}, {41, 1}, {42, 1}, {43, 1}, {44, 1}, {45, 1}, {46, 1}, {47, 1}, {48, 1}, {49, 1}, {50, 1}, {51, 1}, {52, 1}, {53, 1}, {54, 1}, {55, 1}, {56, 1}, {57, 1}, {58, 1}, {59, 1}, {60, 1}, {61, 1}, {62, 1}, {63, 1}, {64, 1}, {65, 1}, {66, 1}, {67, 1}, {68, 1}, {69, 1}, {70, 1}, {71, 1}, {72, 1}, {73, 1}, {74, 1}, {75, 1}, {76, 1}, {77, 1}, {78, 1}, {79, 1}, {80, 1}, {81, 1}, {82, 1}, {83, 1}, {84, 1}, {85, 1}, {86, 1}, {87, 1}, {88, 1}, {89, 1}, {90, 1}, {91, 1}, {92, 1}, {93, 1}, {94, 1}, {95, 1}, {96, 1}, {97, 1}, {98, 1}, {99, 1}, {100, 1}, {101, 1}, {102, 1}, {103, 1}, {104, 1}, {105, 1}, {106, 1}, {107, 1}, {108, 1}, {109, 1}, {110, 1}, {111, 1}, {112, 1}, {113, 1}, {116, 1}, {119, 1}};
    // for (int a = 0; a < n; ++a) {
    //     for (int b = 1; b <= n; ++b) {
    //         if (a + b * 2 <= 124) {
    //             for (int i = 0; i < n; ++i) {
    //                 if (i >= a && i % b == a % b) {
    //                     bs[qs.size()][i] = 1;
    //                 } else {
    //                     bs[qs.size()][i] = 0;
    //                 }
    //             }
    //             if (is_answer(qs.size(), n)) {
    //                 qs.emplace_back(a, b);
    //             }
    //         }
    //         if (qs.size() == n) {
    //             break;
    //         }
    //     }
    //     if (qs.size() == n) {
    //         break;
    //     }
    // }
    // cout << "{";
    // for (int i = 0; i < n; ++i) {
    //     cout << "{" << qs[i].first << ", " << qs[i].second << "}";
    //     if (i + 1 < n) {
    //         cout << ", ";
    //     }
    // }
    // cout << "}";
    if (qs.size() != n) {
        return "";
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j >= qs[i].first && j % qs[i].second == qs[i].first % qs[i].second) {
                bs[i][j] = 1;
            } else {
                bs[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        vector<int> a(qs[i].first + qs[i].second * 2), b(qs[i].first + qs[i].second * 2);
        for (int j = 0; j < qs[i].first; ++j) {
            a[j] = b[j] = j + 1;
        }
        for (int j = 0; j < qs[i].second; ++j) {
            if (j + 1 == qs[i].second) {
                a[qs[i].first + j] = b[qs[i].first + j] = qs[i].first;
                a[qs[i].first + qs[i].second + j] = b[qs[i].first + qs[i].second + j] = qs[i].first + qs[i].second;
            } else {
                a[qs[i].first + j] = b[qs[i].first + j] = qs[i].first + j + 1;
                a[qs[i].first + qs[i].second + j] = b[qs[i].first + qs[i].second + j] = qs[i].first + qs[i].second + j + 1;
            }
        }
        b[qs[i].first] = qs[i].first + qs[i].second + 1;
        b[qs[i].first + qs[i].second] = qs[i].first + 1;
        if (qs[i].second == 1) {
            b[qs[i].first]--;
            b[qs[i].first + qs[i].second]--;
        }
        int val = Query(qs[i].first + qs[i].second * 2, a, b);
        if (val < qs[i].first + qs[i].second) {
            bs[i][n] = 0;
        } else {
            bs[i][n] = 1;
        }
    }
    return get_answer(n);
}

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:88:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |     if (qs.size() != n) {
      |         ~~~~~~~~~~^~~~

• Subtask 1: 95 / 100