Submission #952204

#	Time	Username	Problem	Language	Result	Execution time	Memory
952204		arbuzick	Ancient Machine 2 (JOI23_ancient2)	C++17	94 / 100	448 ms	1072 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;
    for (int a = 0; a < n; ++a) {
        for (int b = 1; b <= n; ++b) {
            if (a + b * 2 <= 130) {
                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;
        }
    }
    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:72: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]
   72 |             if (qs.size() == n) {
      |                 ~~~~~~~~~~^~~~
ancient2.cpp:76: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]
   76 |         if (qs.size() == n) {
      |             ~~~~~~~~~~^~~~
ancient2.cpp:80: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]
   80 |     if (qs.size() != n) {
      |         ~~~~~~~~~~^~~~

• Subtask 1: 94 / 100