Submission #938810

#	Time	Username	Problem	Language	Result	Execution time	Memory
938810		anton	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	43 ms	1464 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);
  }
}

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);
  }
}


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;

  //cout<<oc[citizen]<<endl;
  for(int i = 0; i<oc[citizen]; i++){
    vector<vector<int>> v(2);
    add_delay(citizen, i+2, v);
    citizen_pos.push_back(n-find_remaining(v));
  }
  for(auto e: citizen_pos){
    //cout<<e<<endl;
    s[e]= (char)('0'+citizen);
  }
  //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 'int chines_remainders(int, int, int, int)':
ancient2.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

• Subtask 1: 0 / 100