oj.uz

Submission #965156

# Submission time Handle Problem Language Result Execution time Memory
965156 2024-04-18T07:49:49 Z Pring Ancient Machine 2 (JOI23_ancient2) C++17
37 / 100
 48 ms 1864 KB 
#include <bits/stdc++.h>
#include "ancient2.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {

    string FIRST() {
        return (Query(3, {1, 1, 2}, {2, 1, 2}) == 1 ? "0" : "1");
    }

    pair<vector<int>, vector<int>> COMPRESS(string s) {
        vector<int> a, b;
        int n = s.size(), id = 0;
        while (id < n) {
            if (id == n - 1) {
                a.push_back(a.size() + (s[id] == '0'));
                b.push_back(b.size() + (s[id] == '1'));
                id++;
            } else {
                int r = id;
                while (s[r] == s[id]) r++;
                a.push_back(a.size() + (s[id] == '1'));
                b.push_back(b.size() + (s[id] == '0'));
                id = r + 1;
            }
        }
        return mp(a, b);
    }

    int Q1(vector<int> a, vector<int> b, bool INV) {
        vector<int> va = {1, 2, 3, 3, 4, 5, 6, 7};
        vector<int> vb = {4, 5, 6, 7, 4, 5, 6, 7};
        int m = a.size();
        for (auto &i : va) a.push_back(i + m);
        for (auto &i : vb) b.push_back(i + m);
        // debug(INV);
        // for (auto &i : a) cout << i << ' ';
        // cout << endl;
        // for (auto &i : b) cout << i << ' ';
        // cout << endl;
        int res = (INV ? Query(m + 8, b, a) : Query(m + 8, a, b));
        // debug();
        if (res == m + 7) return -1;
        return max(0, res - m - 3);
    }

    int GROUP(vector<int> a, vector<int> b, int G, bool INV) {
        vector<int> va, vb;
        FOR(i, 0, G - 1) va.push_back(i + 1);
        va.push_back(0);
        FOR(i, 0, G) va.push_back(i + G);
        FOR(i, 0, G) vb.push_back(i + G);
        FOR(i, 0, G) vb.push_back(i + G);
        int m = a.size();
        for (auto &i : va) a.push_back(i + m);
        for (auto &i : vb) b.push_back(i + m);
        int res = (INV ? Query(m + G * 2, b, a) : Query(m + G * 2, a, b));
        return res - m - G;
    }

    int CRT(vector<int> a, vector<int> b, bool INV) {
        int x = GROUP(a, b, 7, INV);
        int y = GROUP(a, b, 11, INV);
        int z = GROUP(a, b, 13, INV);
        return (715 * x + 364 * y + 924 * z) % 1001;
    }

    string GET(vector<int> &a, vector<int> &b, char c) {
        if (c & 1) swap(a, b);
        int res = Q1(a, b, c & 1);
        // debug(res);
        if (res != -1) {
            if (res == 0) return string(1005, c);
            string ans;
            ans = string(res - 1, c);
            ans.push_back(c ^ 1);
            return ans;
        }
        res = CRT(a, b, c & 1);
        string ans = string(res, c);
        ans.push_back(c ^ 1);
        return ans;
    }

    string miku(int n) {
        string ans = FIRST();
        while (ans.size() < n) {
            auto [va, vb] = COMPRESS(ans);
            // debug(ans);
            // for (auto &i : va) cout << i << ' ';
            // cout << endl;
            // for (auto &i : vb) cout << i << ' ';
            // cout << endl;
            string s = GET(va, vb, ans.back());
            // ans.pop_back();
            ans += s;
            while (ans.size() > n) ans.pop_back();
            debug(ans);
        }
        debug(ans);
        return ans;
    }
}

string Solve(int n) {
    return miku(n);
}

Compilation message

ancient2.cpp: In function 'std::string {anonymous}::miku(int)':
ancient2.cpp:104:27: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |         while (ans.size() < n) {
      |                ~~~~~~~~~~~^~~
ancient2.cpp:114:31: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |             while (ans.size() > n) ans.pop_back();
      |                    ~~~~~~~~~~~^~~
ancient2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
ancient2.cpp:115:13: note: in expansion of macro 'debug'
  115 |             debug(ans);
      |             ^~~~~
ancient2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 39
      |                    ^~
ancient2.cpp:117:9: note: in expansion of macro 'debug'
  117 |         debug(ans);
      |         ^~~~~

Subtask #1
37.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 1288 KB Output is partially correct
2 Partially correct 9 ms 796 KB Output is partially correct
3 Partially correct 8 ms 796 KB Output is partially correct
4 Partially correct 6 ms 1260 KB Output is partially correct
5 Partially correct 10 ms 808 KB Output is partially correct
6 Correct 3 ms 968 KB Output is correct
7 Partially correct 17 ms 836 KB Output is partially correct
8 Partially correct 45 ms 1068 KB Output is partially correct
9 Partially correct 12 ms 1228 KB Output is partially correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 2 ms 708 KB Output is correct
13 Correct 3 ms 464 KB Output is correct
14 Correct 2 ms 452 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Partially correct 48 ms 800 KB Output is partially correct
17 Partially correct 45 ms 1040 KB Output is partially correct
18 Partially correct 37 ms 876 KB Output is partially correct
19 Partially correct 45 ms 1044 KB Output is partially correct
20 Partially correct 43 ms 1280 KB Output is partially correct
21 Partially correct 36 ms 984 KB Output is partially correct
22 Partially correct 11 ms 1072 KB Output is partially correct
23 Partially correct 12 ms 1340 KB Output is partially correct
24 Partially correct 10 ms 1072 KB Output is partially correct
25 Partially correct 14 ms 1064 KB Output is partially correct
26 Partially correct 12 ms 808 KB Output is partially correct
27 Partially correct 11 ms 816 KB Output is partially correct
28 Partially correct 11 ms 1324 KB Output is partially correct
29 Partially correct 12 ms 1044 KB Output is partially correct
30 Partially correct 22 ms 1300 KB Output is partially correct
31 Partially correct 8 ms 704 KB Output is partially correct
32 Correct 3 ms 632 KB Output is correct
33 Correct 2 ms 708 KB Output is correct
34 Correct 1 ms 452 KB Output is correct
35 Correct 1 ms 716 KB Output is correct
36 Correct 1 ms 344 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Partially correct 22 ms 1576 KB Output is partially correct
39 Partially correct 22 ms 1352 KB Output is partially correct
40 Partially correct 19 ms 1096 KB Output is partially correct
41 Partially correct 21 ms 1012 KB Output is partially correct
42 Partially correct 22 ms 1276 KB Output is partially correct
43 Partially correct 23 ms 704 KB Output is partially correct
44 Partially correct 22 ms 1504 KB Output is partially correct
45 Partially correct 22 ms 1272 KB Output is partially correct
46 Partially correct 22 ms 988 KB Output is partially correct
47 Partially correct 22 ms 1864 KB Output is partially correct
48 Partially correct 22 ms 1608 KB Output is partially correct
49 Partially correct 23 ms 1108 KB Output is partially correct
50 Partially correct 19 ms 1336 KB Output is partially correct
51 Partially correct 21 ms 856 KB Output is partially correct
52 Partially correct 24 ms 1356 KB Output is partially correct
53 Partially correct 19 ms 1100 KB Output is partially correct
54 Partially correct 20 ms 1088 KB Output is partially correct
55 Partially correct 22 ms 1096 KB Output is partially correct
56 Partially correct 19 ms 1596 KB Output is partially correct
57 Correct 3 ms 728 KB Output is correct
58 Partially correct 23 ms 856 KB Output is partially correct
59 Correct 1 ms 600 KB Output is correct
60 Partially correct 7 ms 980 KB Output is partially correct
61 Partially correct 12 ms 1292 KB Output is partially correct
62 Partially correct 22 ms 1112 KB Output is partially correct
63 Partially correct 17 ms 1052 KB Output is partially correct