Submission #952195

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
952195	2024-03-23T09:24:36 Z	arbuzick	Ancient Machine 2 (JOI23_ancient2)	C++17	64 / 100	649 ms	1668 KB

ancient2

#include "ancient2.h"

#include <bits/stdc++.h>

using namespace std;

bitset<1001> bs[1000];

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

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 <= 302) {
                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() + 1, 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

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:70: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]
   70 |             if (qs.size() == n) {
      |                 ~~~~~~~~~~^~~~
ancient2.cpp:74: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]
   74 |         if (qs.size() == n) {
      |             ~~~~~~~~~~^~~~
ancient2.cpp:78: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]
   78 |     if (qs.size() != n) {
      |         ~~~~~~~~~~^~~~

Subtask #1

64.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	584 ms	460 KB	Output is partially correct
2	Partially correct	582 ms	1176 KB	Output is partially correct
3	Partially correct	598 ms	924 KB	Output is partially correct
4	Partially correct	591 ms	928 KB	Output is partially correct
5	Partially correct	586 ms	1104 KB	Output is partially correct
6	Partially correct	589 ms	672 KB	Output is partially correct
7	Partially correct	605 ms	924 KB	Output is partially correct
8	Partially correct	587 ms	676 KB	Output is partially correct
9	Partially correct	586 ms	976 KB	Output is partially correct
10	Partially correct	603 ms	1112 KB	Output is partially correct
11	Partially correct	588 ms	924 KB	Output is partially correct
12	Partially correct	577 ms	928 KB	Output is partially correct
13	Partially correct	595 ms	1136 KB	Output is partially correct
14	Partially correct	597 ms	916 KB	Output is partially correct
15	Partially correct	591 ms	884 KB	Output is partially correct
16	Partially correct	590 ms	916 KB	Output is partially correct
17	Partially correct	584 ms	924 KB	Output is partially correct
18	Partially correct	596 ms	1160 KB	Output is partially correct
19	Partially correct	616 ms	976 KB	Output is partially correct
20	Partially correct	599 ms	820 KB	Output is partially correct
21	Partially correct	633 ms	1668 KB	Output is partially correct
22	Partially correct	608 ms	880 KB	Output is partially correct
23	Partially correct	603 ms	908 KB	Output is partially correct
24	Partially correct	649 ms	832 KB	Output is partially correct
25	Partially correct	589 ms	672 KB	Output is partially correct
26	Partially correct	590 ms	928 KB	Output is partially correct
27	Partially correct	578 ms	924 KB	Output is partially correct
28	Partially correct	599 ms	924 KB	Output is partially correct
29	Partially correct	639 ms	1176 KB	Output is partially correct
30	Partially correct	638 ms	836 KB	Output is partially correct
31	Partially correct	603 ms	1332 KB	Output is partially correct
32	Partially correct	583 ms	928 KB	Output is partially correct
33	Partially correct	609 ms	924 KB	Output is partially correct
34	Partially correct	597 ms	756 KB	Output is partially correct
35	Partially correct	607 ms	932 KB	Output is partially correct
36	Partially correct	604 ms	972 KB	Output is partially correct
37	Partially correct	582 ms	676 KB	Output is partially correct
38	Partially correct	618 ms	924 KB	Output is partially correct
39	Partially correct	645 ms	672 KB	Output is partially correct
40	Partially correct	590 ms	924 KB	Output is partially correct
41	Partially correct	600 ms	936 KB	Output is partially correct
42	Partially correct	585 ms	920 KB	Output is partially correct
43	Partially correct	583 ms	672 KB	Output is partially correct
44	Partially correct	599 ms	736 KB	Output is partially correct
45	Partially correct	605 ms	968 KB	Output is partially correct
46	Partially correct	582 ms	924 KB	Output is partially correct
47	Partially correct	575 ms	680 KB	Output is partially correct
48	Partially correct	596 ms	856 KB	Output is partially correct
49	Partially correct	599 ms	720 KB	Output is partially correct
50	Partially correct	590 ms	860 KB	Output is partially correct
51	Partially correct	581 ms	924 KB	Output is partially correct
52	Partially correct	576 ms	928 KB	Output is partially correct
53	Partially correct	594 ms	1280 KB	Output is partially correct
54	Partially correct	590 ms	1032 KB	Output is partially correct
55	Partially correct	587 ms	724 KB	Output is partially correct
56	Partially correct	586 ms	932 KB	Output is partially correct
57	Partially correct	591 ms	676 KB	Output is partially correct
58	Partially correct	595 ms	760 KB	Output is partially correct
59	Partially correct	601 ms	1116 KB	Output is partially correct
60	Partially correct	581 ms	672 KB	Output is partially correct
61	Partially correct	582 ms	676 KB	Output is partially correct
62	Partially correct	594 ms	772 KB	Output is partially correct
63	Partially correct	598 ms	988 KB	Output is partially correct