oj.uz

답안 #952195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952195 2024-03-23T09:24:36 Z arbuzick Ancient Machine 2 (JOI23_ancient2) C++17
64 / 100
 649 ms 1668 KB 
#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

# 결과 실행 시간 메모리 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