Submission #1129306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129306		Zbyszek99	Ancient Machine 2 (JOI23_ancient2)	C++20	100 / 100	51 ms	544 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int MAXN = 1000;

struct equation
{
    bitset<MAXN> eq;
    void operator^=(const equation& other)
    {
        eq ^= other.eq;
    }
};

int n;

equation eq[MAXN];
bool is_used[MAXN];
int eq_count = 0;

bool add_eq(equation new_eq, bool check = false)
{
    rep(i,n)
    {
        if(new_eq.eq[i] == 1)
        {
            if(!is_used[i])
            {
                if(!check)
                {
                    eq[i] = new_eq;
                    is_used[i] = 1;
                    eq_count++;
                }
      //          if(!check) cout << "git\n";
                return 1;
            }
            new_eq ^= eq[i];
        }
    }
    //cout << "boo\n";
    return false;
}

string get_ans()
{
    vi ans(n,0);
    for(int i = n-1; i >= 0; i--)
    {
        int sum = eq[i].eq[n];
        for(int j = i+1; j < n; j++)
        {
            sum ^= (eq[i].eq[j]*ans[j]);
        }
        ans[i] = sum;
    }
    string ans_str;
    rep(i,n) ans_str += (char)('0' + ans[i]);
    return ans_str;
}

void get_eq_kth(int x, int mod)
{
    equation ans;
    for(int i = mod; i < n; i += x)
    {
//        cout << i << " i\n";
        ans.eq[i] = 1;
    }
    if(!add_eq(ans,true)) return;
    int m = x*2;
    vi a(m);
    vi b(m);
   // cout << mod << " mod\n";
    for(int i = 0; i < x*2; i += 2)
    {
        if(i/2 == mod)
        {
            a[i] = (i+2)%(x*2);
            b[i] = (i+3)%(x*2);
            a[i+1] = (i+3)%(x*2);
            b[i+1] = (i+2)%(x*2);
        }
        else
        {
            a[i] = (i+2)%(x*2);
            b[i] = (i+2)%(x*2);
            a[i+1] = (i+3)%(x*2);
            b[i+1] = (i+3)%(x*2);
        }
    }
    int q = Query(m,a,b);
    if(q % 2 == 1)
    {
        ans.eq[n] = 1;
    }
    add_eq(ans);
}

equation get_first_num(int x)
{
    equation ans;
    ans.eq[x] = 1;
    int m = x+3;
    vi a(m);
    vi b(m);
    rep(i,x)
    {
        a[i] = i+1;
        b[i] = i+1;
    }
    a[x] = m-2;
    b[x] = m-1;
    a[m-1] = m-1;
    b[m-1] = m-1;
    a[m-2] = m-2;
    b[m-2] = m-2;
    int q = Query(m,a,b);
  //  cout << q << " q\n";
    if(q == m-1) ans.eq[n] = 1;
    return ans;
}

int find_max_suf(string s, string suf)
{
    string s1,s2;
    int n = siz(suf);
    int ans = 0;
    rep(i,n)
    {
        s1 += s[i];
        s2 = suf[n-1-i] + s2;
        if(s1 == s2) ans = max(ans,i+1);
    }
    return ans;
}

bool is_sufix(string suf)
{
    int m = siz(suf)+1;
    vi a(m);
    vi b(m);
    string cur_suf;
    rep(i,m)
    {
        a[i] = find_max_suf(suf,cur_suf + "0");
        b[i] = find_max_suf(suf,cur_suf + "1");
        if(i != siz(suf)) cur_suf += suf[i];
    }
    int x = Query(m,a,b);
    if(x == m-1) return true;
    return false;
}

string Solve(int N) 
{
    n = N;
    rep(i,100)
    {
        add_eq(get_first_num(i));
        if(eq_count == n) return get_ans();
    }
    string cur_suf = "";
    rep(k,100)
    {
        //cout << cur_suf << " suf\n";
        if(is_sufix("0" + cur_suf))
        {
            equation eq;
            eq.eq[n-k-1] = 1;
            add_eq(eq);
            cur_suf = '0' + cur_suf;
        }
        else
        {
            equation eq;
            eq.eq[n-k-1] = 1;
            eq.eq[n] = 1;
            add_eq(eq);
            cur_suf = '1' + cur_suf;    
        }
        if(eq_count == n) return get_ans();
    }
    rep2(k,1,1000)
    {
        rep(mod,k)
        {
            get_eq_kth(k,mod);
            if(eq_count == n) return get_ans();
        }
    }
}

Compilation message (stderr)

ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:213:1: warning: control reaches end of non-void function [-Wreturn-type]
  213 | }
      | ^

• Subtask 1: 100 / 100