Submission #938845

#	Time	Username	Problem	Language	Result	Execution time	Memory
938845		anton	Ancient Machine 2 (JOI23_ancient2)	C++17	30 / 100	49 ms	1812 KiB

ancient2

#include "ancient2.h"
#include<bits/stdc++.h>


#define ll long long
#define pii pair<int, int>
using namespace std;

int n;


int mQuery(int m, vector<int>&a, vector<int>&b){
  /*cout<<m<<endl;
  for(auto e: a){
    cout<<e<<" ";
  }
  cout<<endl;
  for(auto e: b){
    cout<<e<<" ";
  }
  cout<<endl;*/
  int r= Query(m, a, b);
  //cout<<"res "<<r<<endl
  return r;
}
const int SZ = 700;
map<int, int> simulate(vector<pii>& a, vector<pii>& b, int start, string s){
  int pos = start;
  vector<int> oc(SZ);
  for(int i = 0; i<1000; i++){
    if(s[i] == '0'){
      pos = a[pos].second;
    }
    else{
      pos =b[pos].second;
    }
    oc[pos]++;
  }
  cout<<oc[start]<<" "<<oc[pos]<<endl;
  map<int, int> nb;
  for(int i = 0; i<SZ; i++){
    nb[oc[i]]++;
  }
  return nb;
}

void add_key_check(vector<int>& a, vector<int>& b, string key){
  int begin = a.size()-1;
  vector<vector<int>> ids;
  ids.resize(2, vector<int>(key.size()));

  a.resize(a.size()+2*key.size());
  b.resize(b.size()+2*key.size());
  for(int i = 0; i<key.size()-1; i++){
    if(key[i] == '0'){
      a[begin+i] = begin+i+1;
      b[begin+i] = begin+key.size()+i;
    }
    else{
      b[begin+i] = begin+i+1;
      a[begin+i] = begin+key.size()+i;
    }
  }
}

void add_choice(vector<int>& a, vector<int>& b){
  int begin = a.size()-1;
  a.back() = begin+1;
  b.back() = begin+2;
  for(int i = 1; i<=2; i++){
    a.push_back(i+begin);
    b.push_back(i+begin);
  }
}
void add_double_choice(vector<int>& a, vector<int>& b){
  int begin = a.size()-1;
  //cout<<"begin is "<<begin<<endl;
  a.resize(a.size()+6);
  b.resize(b.size()+6);
  for(int i =1; i<4; i++){
    a[i+begin-1] = begin + 2*i -1;
    b[i+begin-1] = begin + 2*i ;
  }
  for(int i = 4; i<8; i++){
    a[i+begin-1] = i+begin-1;
    b[i+begin-1] = i+begin-1;
  }
}

const ll mod = 1e9 +7;
int oc[2] = {0, 0};

int chines_remainders(int a, int ma, int b, int mb){
  a =a%ma;
  b= b%mb;
  for(int i = 0; i<=1000; i++){
    if(i%ma == a && i%mb ==b){
      return i;
    }
  }
  //cout<<a<<" "<<b<<endl;
}

void find_oc(){ 
  vector<int> a, b;
  for(int i = 0; i<31; i++){
    a.push_back(i);
    b.push_back((i+1)%31);
  }
  int m31 = mQuery(a.size(), a, b);
  a.clear();
  b.clear();
  for(int i = 0; i<37; i++){
    a.push_back(i);
    b.push_back((i+1)%37);
  }
  int m37 = mQuery(a.size(), a, b);

  oc[1] = chines_remainders(m31, 31, m37, 37);
  oc[0] = n-oc[1];
}

int find_remaining(vector<vector<int>>& v){
  auto v1 = v;
  int begin = v[0].size()-1;
  v[0].resize(v[0].size()+30);
  v[1].resize(v[1].size()+30);

  for(int i = 0; i<31; i++){
    v[0][i+begin] =begin +((i+1)%31);
    v[1][i+begin] =begin +((i+1)%31);
  }
  int m31 = mQuery(v[0].size(), v[0], v[1])-begin+1;

  swap(v, v1);

  v[0].resize(v[0].size()+36);
  v[1].resize(v[1].size()+36);

  for(int i = 0; i<37; i++){
    v[0][i+begin] =begin +((i+1)%37);
    v[1][i+begin] =begin +((i+1)%37);
  }
  int m37 = mQuery(v[0].size(), v[0], v[1])-begin+1;

  return chines_remainders(m31, 31, m37, 37);
}

void add_delay(int citizen, int len, vector<vector<int>>& v){
  int exc = (citizen+1)%2;
  for(int i = 0; i<len; i++){
    v[citizen].push_back(i+1);
    v[exc].push_back(i);
  }
}

int find_dist(vector<vector<int>>& v, int citizen){
  auto v1 = v;
  int exc= (citizen+1)%2;
  int begin = v[0].size()-1;
  v[0].resize(v[0].size()+61);
  v[1].resize(v[1].size()+61);

  for(int i = 0; i<31; i++){
    v[exc][2*i+begin] =begin +((2*i+2)%62);
    v[citizen][2*i+begin] =begin +((2*i+1)%62);
    v[exc][2*i+1+begin] = 2*i+1+begin;
    v[citizen][2*i+1+begin] = 2*i+1+begin;
  }
  int m31 = (mQuery(v[0].size(), v[0], v[1])-begin+1)/2;

  swap(v, v1);

  v[0].resize(v[0].size()+73);
  v[1].resize(v[1].size()+73);

  for(int i = 0; i<37; i++){
    v[exc][2*i+begin] =begin +((2*i+2)%74);
    v[citizen][2*i+begin] =begin +((2*i+1)%74);
    v[exc][2*i+1+begin] = 2*i+1+begin;
    v[citizen][2*i+1+begin] = 2*i+1+begin;
  }
  int m37 = (mQuery(v[0].size(), v[0], v[1])-begin+1)/2;

  return chines_remainders(m31, 31, m37, 37);
}


std::string Solve(int N) {
  n= N;
  srand(time(NULL));

  find_oc();
  vector<int> citizen_pos;
  int citizen= 0;
  if(oc[0]>oc[1]){
    citizen = 1;
  }
  
  string s(n, (char)('0'+((citizen+1)%2)));

  //cout<<oc[0]<<" "<<oc[1]<<endl;

  if(oc[citizen]<500){
  //cout<<oc[citizen]<<endl;
    vector<vector<int>> v(2);
    add_delay(citizen,2, v);
    citizen_pos.push_back(n-find_remaining(v));
    for(int i = 1; i<oc[citizen]; i++){
      vector<vector<int>> v(2);
      add_delay(citizen, i+1, v);
      citizen_pos.push_back(citizen_pos.back()+find_dist(v, citizen));
    }
    for(auto e: citizen_pos){
      //cout<<e<<endl;
      s[e]= (char)('0'+citizen);
    }
  }
  else{
    vector<int> pref_oc(2, 0);
    for(int i = 0; i<n; i++){
      vector<vector<int>> v(2);
      if(i>0){
        add_delay(s[i-1]-'0', pref_oc[s[i-1]-'0']+1, v);
      }
      else{  
        v[0].push_back(0);
        v[1].push_back(1);
      }
      if(i<n-1){        
        int base=  v[0].size()-1;

        add_double_choice(v[0], v[1]);
        int r=  mQuery(v[0].size(), v[0], v[1])-base+1;
        //cout<<r<<endl;
        for(int j = 1; j>=0; j--){
          s[i+j] = (char)('0'+(r%2));
          pref_oc[s[i+j]-'0']++;
          r/=2;
        }
        //cout<<s<<endl;
        i++;
      }
      else{
        add_choice(v[0], v[1]);
        int r= mQuery(v[0].size(), v[0], v[1]);
        if(r== v[0].size()-1){
          s[i] ='1';
          pref_oc[1]++;
        }
        else{
          s[i] = '0';
          pref_oc[0]++;
        }
      }
      
    }
  }
  //cout<<s<<endl;
  return s;
}

Compilation message (stderr)

ancient2.cpp: In function 'void add_key_check(std::vector<int>&, std::vector<int>&, std::string)':
ancient2.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i<key.size()-1; i++){
      |                  ~^~~~~~~~~~~~~
ancient2.cpp: In function 'std::string Solve(int)':
ancient2.cpp:247:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  247 |         if(r== v[0].size()-1){
      |            ~^~~~~~~~~~~~~~~~
ancient2.cpp: In function 'int chines_remainders(int, int, int, int)':
ancient2.cpp:102:1: warning: control reaches end of non-void function [-Wreturn-type]
  102 | }
      | ^

• Subtask 1: 30 / 100