Submission #952233

#	Time	Username	Problem	Language	Result	Execution time	Memory
952233		arbuzick	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	336 ms	1272 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) {
    for (int i = 0; i < 100; ++i) {
        bs[i][i] = 1;
    }
    for (int i = 0; i < 101; ++i) {
        bs[100 + i][n - i - 1] = 1;
    }
    vector<pair<int, int>> qs;
    for (int a = 0; a < n; ++a) {
        for (int b = 1; b <= n; ++b) {
            if (a < b && b * 2 <= 102) {
                for (int i = 0; i < n; ++i) {
                    if (i >= a && i % b == a % b) {
                        bs[201 + qs.size()][i] = 1;
                    } else {
                        bs[201 + qs.size()][i] = 0;
                    }
                }
                if (is_answer(201 + qs.size(), n)) {
                    qs.emplace_back(a, b);
                }
            }
            if (qs.size() == n - 201) {
                break;
            }
        }
        if (qs.size() == n - 201) {
            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 - 201) {
        return "";
    }
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j == i) {
                bs[i][j] = 1;
            } else {
                bs[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < 101; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j == n - i - 1) {
                bs[100 + i][j] = 1;
            } else {
                bs[100 + i][j] = 0;
            }
        }
    }
    for (int i = 0; i < (int)qs.size(); ++i) {
        for (int j = 0; j < n; ++j) {
            if (j >= qs[i].first && j % qs[i].second == qs[i].first % qs[i].second) {
                bs[201 + i][j] = 1;
            } else {
                bs[201 + i][j] = 0;
            }
        }
    }
    for (int i = 0; i < 100; ++i) {
        vector<int> a(i + 3), b(i + 3);
        for (int j = 0; j < i; ++j) {
            a[j] = j + 1;
            b[j] = j + 1;
        }
        a[i] = i + 1;
        b[i] = i + 2;
        a[i + 1] = b[i + 1] = i + 1;
        a[i + 2] = b[i + 2] = i + 2;
        int val = Query(i + 3, a, b);
        if (val == i + 1) {
            bs[i][n] = 0;
        } else {
            bs[i][n] = 1;
        }
    }
    string suff = "";
    for (int i = 0; i < 101; ++i) {
        suff = "0" + suff;
        vector<int> a(i + 2), b(i + 2);
        for (int j = 0; j <= i + 1; ++j) {
            string nw = suff.substr(0, j);
            string nw0 = nw + '0';
            string nw1 = nw + '1';
            for (int k = 0; k <= j + 1 && k <= i + 1; ++k) {
                if (nw0.substr((int)nw0.size() - k) == suff.substr(0, k)) {
                    a[j] = k;
                }
                if (nw1.substr((int)nw1.size() - k) == suff.substr(0, k)) {
                    b[j] = k;
                }
            }
        }
        if (Query(i + 2, a, b) == i + 1) {
            bs[100 + i][n] = 0;
        } else {
            bs[100 + i][n] = 1;
            suff = suff.substr(1);
            suff = "1" + suff;
        }
    }
    for (int i = 0; i < (int)qs.size(); ++i) {
        vector<int> a(qs[i].second * 2), b(qs[i].second * 2);
        for (int j = 0; j < qs[i].second; ++j) {
            if (j + 1 == qs[i].second) {
                a[j] = b[j] = 0;
                a[qs[i].second + j] = b[qs[i].second + j] = qs[i].second;
            } else {
                a[j] = b[j] = j + 1;
                a[qs[i].second + j] = b[qs[i].second + j] = qs[i].second + j + 1;
            }
        }
        b[qs[i].first] += qs[i].second;
        b[qs[i].first + qs[i].second] -= qs[i].second;
        int val = Query(qs[i].second * 2, a, b);
        if (val < qs[i].second) {
            bs[201 + i][n] = 0;
        } else {
            bs[201 + i][n] = 1;
        }
    }
    return get_answer(n);
}

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:78:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |             if (qs.size() == n - 201) {
      |                 ~~~~~~~~~~^~~~~~~~~~
ancient2.cpp:82:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if (qs.size() == n - 201) {
      |             ~~~~~~~~~~^~~~~~~~~~
ancient2.cpp:94: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]
   94 |     if (qs.size() != n - 201) {
      |         ~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100