Submission #907461

#	Time	Username	Problem	Language	Result	Execution time	Memory
907461		ibm2006	Minerals (JOI19_minerals)	C++17	100 / 100	156 ms	10488 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,perm[1100000],b[1100000],c[1100000],dp[1100000];
vector<ll> v,u;
void dnc(vector<ll> v,vector<ll> u,ll z)
{
    //printf("(%lld %lld)\n",v.size(),u.size());
    ll i,m=v.size();
    ll mid=m/2,x,y;
    if(m<=900000)
    {
        mid=c[m];
    }
    else if(m<13530)
    {
        mid=3194;
    }
    else if(m<20108)
    {
        mid=5168;
    }
    else if(m<28470)
    {
        mid=8362;
    }
    else
        mid=13530;
        if(z==1)
            mid=m-mid;
        //printf("%lld(%lld)",m,mid);
    vector<ll> v1,v2,u1,u2;
    if(m==1)
    {
        perm[v[0]]=u[0];
        return;
    }
    if(z==0)
    {for(i=0;i<mid;i++)
    {
        //printf("! %lld\n",v[i]);
        x=Query(v[i]);
        s++;
    }}
    else
    {
        for(i=mid;i<m;i++)
        {
            //printf("! %lld\n",v[i]);
            x=Query(v[i]);
            s--;
        }
    }

    for(i=0;i<mid;i++)
    {
        v1.push_back(v[i]);
    }
    for(i=mid;i<m;i++)
    {
        v2.push_back(v[i]);
    }
    x=s-x;
    for(i=0;i<m;i++)
    {
        {
            if(u2.size()==m-mid)
            {
                u1.push_back(u[i]);
                continue;
            }
            if(u1.size()==mid)
                {u2.push_back(u[i]);
                continue;
                }
        }
        //printf("! %lld\n",u[i]);
        y=Query(u[i]);
        if(b[u[i]]==0)
        s++;
        else
            s--;
        b[u[i]]^=1;
        y=s-y;
        //printf("(%lld)\n",y);
        if(y!=x)
            u1.push_back(u[i]);
        else
            u2.push_back(u[i]);
        //    printf("! %lld\n",u[i]);
        x=y;
    }
    dnc(v2,u2,0);
    dnc(v1,u1,1);
}
void f()
{
    ll i,x=0,y;
    for(i=1;i<=n*2;i++)
    {
        y=Query(i);
        t++;
        s++;
        if(y>x)
        {
            v.push_back(i);
            x++;
            continue;
        }
        else
        {
            //Query(i);
            b[i]^=1;
            t++;
            s--;
            u.push_back(i);
            continue;
        }
    }
}
void Solve(ll N) {
   n=N;
   f();
   /*for(i=0;i<v.size();i++)
   {
       Query(v[i]);
   }*/
   dp[1]=0;
    dp[2]=2;
    dp[3]=5;
    c[2]=1;
    c[3]=1;
    //printf("%lld\n",t);
    for(i=4;i<=43000;i++)
    {
        dp[i]=2147483647;
        if(i>=100)
            {l=i/10*3;
            r=i/10*4;
            }
            else
            {
                l=1;
                r=i;
            }
        for(j=l;j<r;j++)
        {
            if(dp[i]>dp[j]+j+dp[i-j]+i-1)
            {
                c[i]=j;
            }
            dp[i]=min(dp[i],dp[j]+j+dp[i-j]+i-1);
        }
    }
    //printf("%lld %lld\n",dp[43000],dp[43000]+t);
   srand(time(NULL));
   random_shuffle(u.begin(),u.end());
   dnc(v,u,1);
   for(i=1;i<=n*2;i++)
   {
       if(perm[i]==0)
        continue;
       Answer(i,perm[i]);
   }
}

Compilation message (stderr)

minerals.cpp: In function 'void dnc(std::vector<int>, std::vector<int>, ll)':
minerals.cpp:28:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   28 |     else
      |     ^~~~
minerals.cpp:30:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   30 |         if(z==1)
      |         ^~
minerals.cpp:68:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   68 |             if(u2.size()==m-mid)
      |                ~~~~~~~~~^~~~~~~
minerals.cpp:73:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   73 |             if(u1.size()==mid)
      |                ~~~~~~~~~^~~~~
minerals.cpp:64:6: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     x=s-x;
      |     ~^~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10