Submission #952233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952233	2024-03-23T10:20:50 Z	arbuzick	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	336 ms	1272 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	314 ms	812 KB	Output is correct
2	Correct	302 ms	568 KB	Output is correct
3	Correct	310 ms	600 KB	Output is correct
4	Correct	313 ms	1012 KB	Output is correct
5	Correct	321 ms	808 KB	Output is correct
6	Correct	325 ms	864 KB	Output is correct
7	Correct	307 ms	812 KB	Output is correct
8	Correct	309 ms	816 KB	Output is correct
9	Correct	312 ms	792 KB	Output is correct
10	Correct	305 ms	820 KB	Output is correct
11	Correct	321 ms	820 KB	Output is correct
12	Correct	326 ms	816 KB	Output is correct
13	Correct	308 ms	952 KB	Output is correct
14	Correct	302 ms	812 KB	Output is correct
15	Correct	315 ms	880 KB	Output is correct
16	Correct	310 ms	572 KB	Output is correct
17	Correct	315 ms	808 KB	Output is correct
18	Correct	324 ms	812 KB	Output is correct
19	Correct	320 ms	592 KB	Output is correct
20	Correct	313 ms	808 KB	Output is correct
21	Correct	309 ms	1032 KB	Output is correct
22	Correct	297 ms	988 KB	Output is correct
23	Correct	306 ms	820 KB	Output is correct
24	Correct	314 ms	560 KB	Output is correct
25	Correct	334 ms	856 KB	Output is correct
26	Correct	303 ms	820 KB	Output is correct
27	Correct	310 ms	560 KB	Output is correct
28	Correct	313 ms	820 KB	Output is correct
29	Correct	310 ms	812 KB	Output is correct
30	Correct	306 ms	816 KB	Output is correct
31	Correct	301 ms	772 KB	Output is correct
32	Correct	321 ms	608 KB	Output is correct
33	Correct	302 ms	876 KB	Output is correct
34	Correct	305 ms	564 KB	Output is correct
35	Correct	307 ms	816 KB	Output is correct
36	Correct	314 ms	824 KB	Output is correct
37	Correct	299 ms	860 KB	Output is correct
38	Correct	305 ms	1032 KB	Output is correct
39	Correct	312 ms	772 KB	Output is correct
40	Correct	302 ms	824 KB	Output is correct
41	Correct	304 ms	816 KB	Output is correct
42	Correct	318 ms	1012 KB	Output is correct
43	Correct	306 ms	616 KB	Output is correct
44	Correct	336 ms	812 KB	Output is correct
45	Correct	322 ms	816 KB	Output is correct
46	Correct	308 ms	816 KB	Output is correct
47	Correct	319 ms	820 KB	Output is correct
48	Correct	312 ms	816 KB	Output is correct
49	Correct	299 ms	772 KB	Output is correct
50	Correct	308 ms	812 KB	Output is correct
51	Correct	313 ms	816 KB	Output is correct
52	Correct	311 ms	628 KB	Output is correct
53	Correct	318 ms	820 KB	Output is correct
54	Correct	323 ms	820 KB	Output is correct
55	Correct	302 ms	592 KB	Output is correct
56	Correct	320 ms	816 KB	Output is correct
57	Correct	320 ms	812 KB	Output is correct
58	Correct	313 ms	812 KB	Output is correct
59	Correct	318 ms	816 KB	Output is correct
60	Correct	309 ms	1272 KB	Output is correct
61	Correct	303 ms	816 KB	Output is correct
62	Correct	300 ms	804 KB	Output is correct
63	Correct	317 ms	568 KB	Output is correct