Submission #815294

#	Time	Username	Problem	Language	Result	Execution time	Memory
815294		minhcool	Ancient Machine 2 (JOI23_ancient2)	C++17	98 / 100	39 ms	624 KiB

ancient2

//#define local
#ifndef local
#include "ancient2.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int n;
 
bitset<1005> basis[1005];
bool vis[1005];
bool ck[1005];
 
string cor;
 
#ifdef local
int Query(int m, vector<int> a, vector<int> b){
    int itr = 0;
    for(int i = 0; i < 1000; i++){
        if(cor[i] == '0') itr = a[itr];
        else itr = b[itr];
        //if(itr == 100) cout << itr << "\n";
    }
}
#endif
 
bool ckk(int p, int q){
    assert(p > q);
    int m = 2 * p;
    vector<int> vc1(m), vc2(m);
    for(int i = 0; i < m; i++) vc1[i] = i + 1;
    vc1[2 * p - 1] = p, vc1[p - 1] = 0;
    vc2 = vc1;
    vc2[q] += p, vc2[q + p] -= p;
    //for(auto it : vc1) assert(it >= 0 && it < m);
    //for(auto it : vc2) assert(it >= 0 && it < m);
    int temp = Query(m, vc1, vc2);
    return (temp >= p);
}
 
int in(bitset<1005> bts){
    bool temp = 0;
    for(int i = 0; i < 1000; i++){
        if(!bts[i]) continue;
        if(!vis[i]){
            vis[i] = 1;
            ck[i] = temp;
            basis[i] = bts;
            return i;
        }
        bts ^= basis[i];
        temp ^= ck[i];
    }
    return -1;
}
 
int cal(bitset<1005> bts){
    bool ans = 0;
    for(int i = 0; i < 1000; i++){
        if(!bts[i]) continue;
        bts ^= basis[i];
        ans ^= ck[i];
    }
    assert(ans == 0 || ans == 1);
    return ans;
}
 
string s;
 
string Solve(int N){
    n = N;
    s.resize(n);
    int p = 55;
    for(int itr = 0; itr < 100; itr++){
        vector<int> a(itr + 3), b(itr + 3);
        for(int i = 0; i < itr; i++) a[i] = b[i] = i + 1;
        a[itr] = itr + 1;
        b[itr] = itr + 2;
        a[itr + 1] = b[itr + 1] = itr + 1;
        a[itr + 2] = b[itr + 2] = itr + 2;
        int temp = Query(itr + 3, a, b);
        if(temp == itr + 1) s[itr] = '0';
        else s[itr] = '1';
    }
    //return "";
    /*
    for(int itr = 100; itr < 200; itr++){
        vector<int> a(101), b(101);
        for(int i = 0; i < 99; i++) a[i] = b[i] = i + 1;
        a[99] = b[99] = 0;
        if(s[itr - 100] == '0') b[itr - 100] = 100;
        else a[itr - 100] = 100;
        a[100] = b[100] = 100;
        int temp = Query(101, a, b);
        cout << itr << " " << temp << "\n";
        if(temp == 100) s[itr] = char(97 - s[itr - 100]);
        else s[itr] = s[itr - 100];
    }*/
    //return "";
    for(int itr = 0; itr < 100; itr++){
        bitset<1005> bts;
        for(int i = 0; i <= 1000; i++) bts[i] = 0;
        bts[itr] = 1;
        int pos = in(bts);
        if(pos < 0) continue;
        if(s[itr] == '1') ck[itr] ^= 1;
    }
    //return "";
    int cnt = 0;
    for(int l = 1; l <= 55; l++){
        for(int r = 0; r < l; r++){
            bitset<1005> bts;
            for(int i = 0; i <= 1000; i++) bts[i] = 0;
            for(int i = r; i <= 1000; i += l) bts[i] = 1;
            int temp = in(bts);
            if(temp < 0) continue;
            //cout << l << " " << r << "\n";
            cnt++;
            bool temp2 = ckk(l, r);
            ck[temp] ^= temp2;
            if(cnt == 900) break;
        }
       // cout << l << " " << cnt << "\n";
        if(cnt == 900) break;
    }
    //cout << cnt << "\n";
    for(int i = 100; i < 1000; i++){
        bitset<1005> bts;
        bts[i] = 1;
        s[i] = char(48 + cal(bts));
    }
    //for(int i = 0; i < 200; i++) assert(s[i] >= '0' && s[i] <= '1');
    return s;
}
 
#ifdef local
void process(){
    cor = "1111111111111010101111111111111111111100000000001111010101010010000000001111110000000001000000011110011111111000111111111101101000000111111111010101010101111111111010101010111111111101010100000000000101010111111111111100000000000000011110111111110111111100000100000000000011100000000000000000000000000000111111010000000001010101000000000000000010101111111111111000000010000000001000000001010101010101000000011111110101010101101010100000000010101011111111111111100000000000000111110101010010101010000000101111111111111111111100001010101111111111111111011111111111010101010101111111111101010101010101010111111111110000000000101011000000011111111101111100000000000000000000000111111100000000011111111110000111111100000000000000000010101010100000000001010100010101011111111111111111101010101010000110100010101001111111111110101000000000000000000000000000000011111111111100001111111101010101010000011111111111000111111100000000011111111111100111111100000000101001011010101111111100000101010101000000000000";
    cout << cor.substr(100) << "\n";
    cout << Solve(1000).substr(100) << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

Compilation message (stderr)

ancient2.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:96:9: warning: unused variable 'p' [-Wunused-variable]
   96 |     int p = 55;
      |         ^

• Subtask 1: 98 / 100