Submission #965156

#	Time	Username	Problem	Language	Result	Execution time	Memory
965156		Pring	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	48 ms	1864 KiB

ancient2

#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 (stderr)

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 / 100