#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);
}
}
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;
//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);
}
//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 'int chines_remainders(int, int, int, int)':
ancient2.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
88 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
49 ms |
1432 KB |
Output is partially correct |
| 2 |
Incorrect |
48 ms |
1556 KB |
Wrong Answer [7] |
| 3 |
Halted |
0 ms |
0 KB |
- |
