#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int used=0;
int colour[nmax]={0,1,2,3,3,1,2,4,4};
int cnt[nmax];
bool in[nmax];
int CURRENT;
/*
int Query(int pos)
{
used++;
CURRENT=CURRENT-(cnt[colour[pos]]>0);
if(in[pos])
{
in[pos]=0;
cnt[colour[pos]]--;
}
else
{
in[pos]=1;
cnt[colour[pos]]++;
}
CURRENT=CURRENT+(cnt[colour[pos]]>0);
return CURRENT;
}
void Answer(int a,int b)
{
return;
cout<<a<<" "<<b<<endl;
}
*/
mt19937 rng(42);
vector< pair<int,int> > outp;
int current=0;
int which_is_active(int le,int ri)
{
if(le)return 0;
return 1;
}
const int MX=1000;
int opt[MX]={0,0,1,1,1,1,1,3,3,1};
double exp_time[MX][MX];
double dp_time[MX];
double coeff=/*(1+sqrt(5))/2+1*/2.6246;
void solve(vector<int> lhs,vector<int> rhs,bool active_lhs)
{
shuffle(rhs.begin(),rhs.end(),rng);
if(lhs.size()==1)
{
outp.push_back({lhs[0],rhs[0]});
return;
}
int mid=lhs.size()/2;
if(lhs.size()<MX)mid=opt[lhs.size()];
else mid=lhs.size()/coeff;
vector<int> lhs_new[2],rhs_new[2];
lhs_new[0]={};lhs_new[1]={};
rhs_new[0]={};rhs_new[1]={};
for(int i=0;i<mid;i++)
{
int mem=Query(lhs[i]);
current=mem;
lhs_new[0].push_back(lhs[i]);
}
for(int i=mid;i<lhs.size();i++)
lhs_new[1].push_back(lhs[i]);
bool type_lhs[2]={!active_lhs,active_lhs};
for(auto k:rhs)
{
if(rhs_new[0].size()==lhs_new[0].size())rhs_new[1].push_back(k);
else if(rhs_new[1].size()==lhs_new[1].size())rhs_new[0].push_back(k);
else
{
int mem=Query(k);
if(current==mem)rhs_new[which_is_active(type_lhs[0],type_lhs[1])].push_back(k);
else rhs_new[!which_is_active(type_lhs[0],type_lhs[1])].push_back(k);
current=mem;
}
}
solve(lhs_new[0],rhs_new[0],type_lhs[0]);
solve(lhs_new[1],rhs_new[1],type_lhs[1]);
}
void Solve(int n)
{
for(int r=1;r<MX;r++)
for(int b=1;b<MX;b++)
{
exp_time[r][b]=1+exp_time[r-1][b]*r/(r+b)+exp_time[r][b-1]*b/(r+b);
}
for(int n_now=2;n_now<MX;n_now++)
{
dp_time[n_now]=1e9;
for(int mid=1;mid<n_now;mid++)
{
double now=dp_time[mid]+dp_time[n_now-mid]+mid+exp_time[mid][n_now-mid];
if(dp_time[n_now]>now)
{
opt[n_now]=mid;
dp_time[n_now]=now;
}
}
}
vector<int> lhs={},rhs={};
for(int i=1;i<=2*n;i++)
{
int mem=Query(i);
if(current<mem)lhs.push_back(i);
else rhs.push_back(i);
current=mem;
}
solve(lhs,rhs,1);
for(int i=0;i<n;i++)
Answer(outp[i].first,outp[i].second);
}
/*
int n;
void create()
{
for(int i=1;i<=n;i++)
colour[i]=i;
for(int i=n+1;i<=2*n;i++)
colour[i]=i-n;
shuffle(colour+1,colour+2*n+1,rng);
}
int main()
{
n=4.3e4;
create();
Solve(n);
cout<<"used= "<<used<<endl;
return 0;
}
*/
Compilation message
minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mid;i<lhs.size();i++)
~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
8320 KB |
Output is correct |
2 |
Correct |
23 ms |
8320 KB |
Output is correct |
3 |
Correct |
26 ms |
8576 KB |
Output is correct |
4 |
Correct |
33 ms |
8952 KB |
Output is correct |
5 |
Correct |
49 ms |
9592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
19 |
Correct |
91 ms |
11668 KB |
Output is correct |
20 |
Correct |
93 ms |
11660 KB |
Output is correct |
21 |
Correct |
92 ms |
11668 KB |
Output is correct |
22 |
Correct |
88 ms |
11540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
19 |
Correct |
91 ms |
11668 KB |
Output is correct |
20 |
Correct |
93 ms |
11660 KB |
Output is correct |
21 |
Correct |
92 ms |
11668 KB |
Output is correct |
22 |
Correct |
88 ms |
11540 KB |
Output is correct |
23 |
Correct |
94 ms |
11716 KB |
Output is correct |
24 |
Correct |
95 ms |
11716 KB |
Output is correct |
25 |
Correct |
93 ms |
11760 KB |
Output is correct |
26 |
Correct |
91 ms |
11532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
19 |
Correct |
91 ms |
11668 KB |
Output is correct |
20 |
Correct |
93 ms |
11660 KB |
Output is correct |
21 |
Correct |
92 ms |
11668 KB |
Output is correct |
22 |
Correct |
88 ms |
11540 KB |
Output is correct |
23 |
Correct |
94 ms |
11716 KB |
Output is correct |
24 |
Correct |
95 ms |
11716 KB |
Output is correct |
25 |
Correct |
93 ms |
11760 KB |
Output is correct |
26 |
Correct |
91 ms |
11532 KB |
Output is correct |
27 |
Correct |
109 ms |
11704 KB |
Output is correct |
28 |
Correct |
99 ms |
11664 KB |
Output is correct |
29 |
Correct |
92 ms |
11724 KB |
Output is correct |
30 |
Correct |
91 ms |
11600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
19 |
Correct |
91 ms |
11668 KB |
Output is correct |
20 |
Correct |
93 ms |
11660 KB |
Output is correct |
21 |
Correct |
92 ms |
11668 KB |
Output is correct |
22 |
Correct |
88 ms |
11540 KB |
Output is correct |
23 |
Correct |
94 ms |
11716 KB |
Output is correct |
24 |
Correct |
95 ms |
11716 KB |
Output is correct |
25 |
Correct |
93 ms |
11760 KB |
Output is correct |
26 |
Correct |
91 ms |
11532 KB |
Output is correct |
27 |
Correct |
109 ms |
11704 KB |
Output is correct |
28 |
Correct |
99 ms |
11664 KB |
Output is correct |
29 |
Correct |
92 ms |
11724 KB |
Output is correct |
30 |
Correct |
91 ms |
11600 KB |
Output is correct |
31 |
Correct |
101 ms |
11688 KB |
Output is correct |
32 |
Correct |
97 ms |
11776 KB |
Output is correct |
33 |
Correct |
98 ms |
11772 KB |
Output is correct |
34 |
Correct |
99 ms |
11580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
8192 KB |
Output is correct |
2 |
Correct |
20 ms |
8192 KB |
Output is correct |
3 |
Correct |
20 ms |
8192 KB |
Output is correct |
4 |
Correct |
20 ms |
8192 KB |
Output is correct |
5 |
Correct |
21 ms |
8320 KB |
Output is correct |
6 |
Correct |
23 ms |
8320 KB |
Output is correct |
7 |
Correct |
26 ms |
8576 KB |
Output is correct |
8 |
Correct |
33 ms |
8952 KB |
Output is correct |
9 |
Correct |
49 ms |
9592 KB |
Output is correct |
10 |
Correct |
21 ms |
8320 KB |
Output is correct |
11 |
Correct |
37 ms |
9208 KB |
Output is correct |
12 |
Correct |
48 ms |
9572 KB |
Output is correct |
13 |
Correct |
44 ms |
9656 KB |
Output is correct |
14 |
Correct |
46 ms |
9568 KB |
Output is correct |
15 |
Correct |
96 ms |
11540 KB |
Output is correct |
16 |
Correct |
90 ms |
11608 KB |
Output is correct |
17 |
Correct |
86 ms |
11568 KB |
Output is correct |
18 |
Correct |
88 ms |
11396 KB |
Output is correct |
19 |
Correct |
91 ms |
11668 KB |
Output is correct |
20 |
Correct |
93 ms |
11660 KB |
Output is correct |
21 |
Correct |
92 ms |
11668 KB |
Output is correct |
22 |
Correct |
88 ms |
11540 KB |
Output is correct |
23 |
Correct |
94 ms |
11716 KB |
Output is correct |
24 |
Correct |
95 ms |
11716 KB |
Output is correct |
25 |
Correct |
93 ms |
11760 KB |
Output is correct |
26 |
Correct |
91 ms |
11532 KB |
Output is correct |
27 |
Correct |
109 ms |
11704 KB |
Output is correct |
28 |
Correct |
99 ms |
11664 KB |
Output is correct |
29 |
Correct |
92 ms |
11724 KB |
Output is correct |
30 |
Correct |
91 ms |
11600 KB |
Output is correct |
31 |
Correct |
101 ms |
11688 KB |
Output is correct |
32 |
Correct |
97 ms |
11776 KB |
Output is correct |
33 |
Correct |
98 ms |
11772 KB |
Output is correct |
34 |
Correct |
99 ms |
11580 KB |
Output is correct |
35 |
Correct |
109 ms |
11940 KB |
Output is correct |
36 |
Correct |
101 ms |
11920 KB |
Output is correct |
37 |
Correct |
102 ms |
11920 KB |
Output is correct |
38 |
Correct |
102 ms |
11788 KB |
Output is correct |