oj.uz

Submission #938845

# Submission time Handle Problem Language Result Execution time Memory
938845 2024-03-05T16:19:29 Z anton Ancient Machine 2 (JOI23_ancient2) C++17
30 / 100
 49 ms 1812 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 45 ms 1060 KB Output is partially correct
2 Partially correct 20 ms 1008 KB Output is partially correct
3 Partially correct 46 ms 832 KB Output is partially correct
4 Partially correct 45 ms 1316 KB Output is partially correct
5 Partially correct 48 ms 984 KB Output is partially correct
6 Partially correct 49 ms 836 KB Output is partially correct
7 Partially correct 20 ms 668 KB Output is partially correct
8 Partially correct 44 ms 1080 KB Output is partially correct
9 Partially correct 44 ms 1068 KB Output is partially correct
10 Partially correct 19 ms 508 KB Output is partially correct
11 Partially correct 19 ms 756 KB Output is partially correct
12 Partially correct 47 ms 1264 KB Output is partially correct
13 Partially correct 43 ms 1308 KB Output is partially correct
14 Partially correct 45 ms 1256 KB Output is partially correct
15 Partially correct 43 ms 1068 KB Output is partially correct
16 Partially correct 21 ms 508 KB Output is partially correct
17 Partially correct 19 ms 508 KB Output is partially correct
18 Partially correct 45 ms 1252 KB Output is partially correct
19 Partially correct 44 ms 1068 KB Output is partially correct
20 Partially correct 46 ms 1424 KB Output is partially correct
21 Partially correct 44 ms 848 KB Output is partially correct
22 Partially correct 45 ms 824 KB Output is partially correct
23 Partially correct 45 ms 828 KB Output is partially correct
24 Partially correct 45 ms 1048 KB Output is partially correct
25 Partially correct 46 ms 828 KB Output is partially correct
26 Partially correct 44 ms 1332 KB Output is partially correct
27 Partially correct 48 ms 828 KB Output is partially correct
28 Partially correct 44 ms 1072 KB Output is partially correct
29 Partially correct 48 ms 1072 KB Output is partially correct
30 Partially correct 43 ms 1068 KB Output is partially correct
31 Partially correct 44 ms 824 KB Output is partially correct
32 Partially correct 35 ms 1068 KB Output is partially correct
33 Partially correct 43 ms 832 KB Output is partially correct
34 Partially correct 46 ms 1312 KB Output is partially correct
35 Partially correct 38 ms 1072 KB Output is partially correct
36 Partially correct 34 ms 1252 KB Output is partially correct
37 Partially correct 30 ms 1084 KB Output is partially correct
38 Partially correct 21 ms 1288 KB Output is partially correct
39 Partially correct 21 ms 736 KB Output is partially correct
40 Partially correct 19 ms 504 KB Output is partially correct
41 Partially correct 20 ms 508 KB Output is partially correct
42 Partially correct 20 ms 500 KB Output is partially correct
43 Partially correct 21 ms 764 KB Output is partially correct
44 Partially correct 19 ms 1012 KB Output is partially correct
45 Partially correct 49 ms 1312 KB Output is partially correct
46 Partially correct 45 ms 820 KB Output is partially correct
47 Partially correct 42 ms 1320 KB Output is partially correct
48 Partially correct 43 ms 1084 KB Output is partially correct
49 Partially correct 48 ms 1032 KB Output is partially correct
50 Partially correct 45 ms 816 KB Output is partially correct
51 Partially correct 44 ms 832 KB Output is partially correct
52 Partially correct 47 ms 1812 KB Output is partially correct
53 Partially correct 44 ms 1316 KB Output is partially correct
54 Partially correct 46 ms 1064 KB Output is partially correct
55 Partially correct 44 ms 812 KB Output is partially correct
56 Partially correct 48 ms 1076 KB Output is partially correct
57 Partially correct 3 ms 716 KB Output is partially correct
58 Partially correct 27 ms 1056 KB Output is partially correct
59 Correct 1 ms 444 KB Output is correct
60 Partially correct 6 ms 1280 KB Output is partially correct
61 Partially correct 11 ms 704 KB Output is partially correct
62 Partially correct 35 ms 1296 KB Output is partially correct
63 Partially correct 19 ms 808 KB Output is partially correct