제출 #938845

#제출 시각아이디문제언어결과실행 시간메모리
938845antonAncient Machine 2 (JOI23_ancient2)C++17
30 / 100
49 ms1812 KiB
#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; }

컴파일 시 표준 에러 (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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...