#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
using namespace std;
///~~~~~~~~~~~~~~~~~~~~~~~~~~
template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> m){
return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> V){
os<<"{";
for(int i=0; i<V.size(); i++){
if(i)os<<" ";
os<<V[i];
}
os<<"}";
return os;
}
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
//#define deb(x...) ;
///~~~~~~~~~~~~~~~~~~~~~~~~~
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int K=17, N=1<<K, INF=1e9+5, mod2=1e9+7, mod=998244353;
struct modint{
int n=0;
modint(){}
modint(ll x){
n=x%mod;
if(n<0)n+=mod;
}
operator int(){
return n;
}
modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;}
modint operator+=(modint a){return (*this)=(*this)+a;}
modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;}
modint operator-=(modint a){return (*this)=(*this)-a;}
modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;}
modint operator*=(modint a){return (*this)=(*this)*a;}
modint operator^(const ll &m)const{
modint a(1);
if(m==0)return a;
if(m==1)return (*this);
a=(*this)^(m/2);
a*=a;
return a*((*this)^(m&1));
}
modint odw(){
return (*this)^((ll)mod-2);
}
modint operator/(modint a){return (*this)*a.odw();}
modint operator/=(modint a){return (*this)=(*this)/a;}
bool operator==(modint a){return a.n==n;}
friend ostream& operator<<(ostream& os, modint m) {
return os << m.n;
}
};
/*modint fact[N], fact2[N];
typedef vector<modint> vm;
void factinit(){
fact[0]=1;
for(int i=1; i<N; i++){
fact[i]=(fact[i-1]*modint(i))%mod;
}
fact2[N-1]=fact[N-1].odw();
for(int i=N-2; i>=0; i--){
fact2[i]=(fact2[i+1]*modint(i+1))%mod;
}
}
modint npok(int _n, int _k){
if(_n<_k)return 0;
return fact[_n]*fact2[_k]*fact2[_n-_k];
}*/
int los(int a, int b){
return a+(rng())%(b-a+1);
}
#include "minerals.h"
/*vi wynik={0, 2, 0, 1, 4, 3, 2, 1, 3, 4};
int czy_w_srodku[N];
int ile_dobrze=0;
int stan[N];
int rozne=0;
int Query(int x){
x--;
czy_w_srodku[x]^=1;
if(czy_w_srodku[x]){
if(!stan[wynik[x]]++)rozne++;
}
else{
if(!--stan[wynik[x]])rozne--;
}
return rozne;
}
void Answer(int a, int b){
deb(a, b, wynik[a-1], wynik[b-1]);
assert(wynik[a-1]==wynik[b-1]);
ile_dobrze++;
}*/
int solve2(vi A, vi B, int wyn, bool b){
//deb(A, B);
if(!A.size())return wyn;
if(A.size()==1){
Answer(A[0], B[0]);
return wyn;
}
vi AL, AR, BL, BR;
for(int i=0; i<A.size(); i++){
if(i || 3*i<A.size()){
AL.pb(A[i]);
wyn=Query(A[i]);
}
else{
AR.pb(A[i]);
//if(b==1)wyn=Query(A[i]);
}
}
int prv=wyn;
for(int i=0; i<B.size(); i++){
if(BL.size()==AL.size()){
BR.pb(B[i]);
continue;
}
if(BR.size()==AR.size()){
BL.pb(B[i]);
continue;
}
int t=Query(B[i]);
if(t!=prv ^ b ^ 1){
BL.pb(B[i]);
}
else BR.pb(B[i]);
prv=t;
}
wyn=solve2(AL, BL, prv, b^1);
wyn=solve2(AR, BR, wyn, b);
return wyn;
}
void solve(vi V){
//deb(V);
if(V.size()==0)return;
if(V.size()==2){
Answer(V[0], V[1]);
return;
}
vi typ(V.size());
vi V2(V.size());
iota(all(V2), 0);
shuffle(all(V2), rng);
int akt=0;
for(int i=0; i<V2.size(); i++){
int now=Query(V[V2[i]]);
if(now!=akt)typ[V2[i]]++;
akt=now;
}
/*shuffle(all(V2), rng);
for(int i=0; i<V.size(); i++){
int now=Query(V[V2[i]]);
if(now!=akt)typ[V2[i]]+=2;
akt=now;
}*/
//deb(typ);
vi L, LL, R, RR;
for(int i=0; i<V.size(); i++){
if(typ[i]==0)L.pb(V[i]);
else if(typ[i]==3)LL.pb(V[i]);
else if(typ[i]==1)R.pb(V[i]);
else RR.pb(V[i]);
}
int a=0;
a=solve2(L, R, a, 1);
//a=solve2(R, RR, a, 0);
}
void Solve(int n){
vector<int> V(n+n);
iota(all(V), 1);
solve(V);
}
/*int main(){
//factinit();
//BOOST
int n=10;
wynik.resize(n+n);
iota(all(wynik), 2);
for(int &i:wynik)i/=2;
assert(wynik.size()==n+n);
shuffle(all(wynik), rng);
deb(wynik);
Solve(n);
assert(ile_dobrze==n);
}*/
Compilation message
minerals.cpp: In function 'int solve2(vi, vi, int, bool)':
minerals.cpp:151:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i=0; i<A.size(); i++){
| ~^~~~~~~~~
minerals.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if(i || 3*i<A.size()){
| ~~~^~~~~~~~~
minerals.cpp:162:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int i=0; i<B.size(); i++){
| ~^~~~~~~~~
minerals.cpp:172:7: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
172 | if(t!=prv ^ b ^ 1){
| ~^~~~~
minerals.cpp: In function 'void solve(vi)':
minerals.cpp:194:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | for(int i=0; i<V2.size(); i++){
| ~^~~~~~~~~~
minerals.cpp:207:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16528 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
53504 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
