oj.uz

Submission #149049

# Submission time Handle Problem Language Result Execution time Memory
149049 2019-09-01T05:38:32 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 571 ms 127480 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=300005;
const int magic=19;
struct line
{
    long long a,b;
    long long ev(long long X,long long Y)
    {
        return (1LL*this->a*X+1LL*this->b*Y);
    }
};
struct srt
{
    int a,b,ind;

}atac[nmax],apar[nmax];
bool comp(srt unu,srt doi)
{
    if(unu.a==doi.a) return unu.b<doi.b;
    return unu.a<doi.a;
}
long double a1,a2,b1,b2;
int lg[nmax];
long double in(line unu,line doi)
{
    a1=unu.a,a2=doi.a,b1=unu.b,b2=doi.b;
    return (b2-b1)/(a1-a2);
}
struct CHT
{
    int u;
    line st[nmax];
    int cb(long double val)
    {
        int ret=0;
        if(u==1)
            return 1;
        for(int pu=lg[u]; pu>=0; pu--)
            if(ret+(1<<pu)<u&&in(st[ret+(1<<pu)],st[ret+(1<<pu)+1])<val)
                ret+=(1<<pu);
        ret++;
        return ret;
    }
    void ins(line dr)
    {
        while(u>=1&&st[u].a==dr.a&&st[u].b<dr.b)
            u--;
        while(u>=2&&in(st[u-1],st[u])>in(st[u-1],dr))
            u--;
        u++;
        st[u]=dr;
    }
}Aa,Dd;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
int n,i;
struct bulaneala
{
    CHT a[2];
    int wh[nmax];
    long double r1,r2;
    int p1,p2;
    void ini(int B)
    {
        int sum=0;
        for(i=0;i<n;i++)
        {
            wh[i]=((i&(1<<B))!=0);
            sum+=wh[i];
        }
        if(sum==0||sum==n)
        {
            int poz=gen()%n;
            wh[poz]^=1;
        }
        for(i=0;i<n;i++)
        {
            if(!wh[atac[i].ind])
                a[0].ins({atac[i].a,atac[i].b});
            if(wh[apar[i].ind])
                a[1].ins({apar[i].a,apar[i].b});
        }
    }
    long long Q(long long X,long long Y)
    {
        r1=X,r2=Y;
        p1=a[0].cb(r1/r2);
        p2=a[1].cb(r1/r2);
        return (a[0].st[p1].ev(X,Y)+a[1].st[p2].ev(X,Y));
    }
}var[magic+2];
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	int N = A.size();
	n=N;
	for(i=2;i<=n;i++)
        lg[i]=lg[i/2]+1;
    for(i=0;i<n;i++)
    {
        atac[i].a=A[i],atac[i].b=P[i],atac[i].ind=i;
        apar[i].a=D[i],apar[i].b=P[i],apar[i].ind=i;
        Aa.ins({A[i],P[i]});
        Dd.ins({D[i],P[i]});
    }
    sort(atac,atac+n,comp);
    sort(apar,apar+n,comp);
    for(int it=0;it<magic;it++)
        var[it].ini(it);
}

long long BestSquad(int X, int Y){
    long long ret=0;
    for(int it=0;it<magic;it++)
        ret=max(ret,var[it].Q(X,Y));
	return ret;
}

Compilation message

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:113:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it=0;it<magic;it++)
     ^~~
squad.cpp:115:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return ret;
  ^~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 562 ms 42380 KB Output is correct
4 Correct 571 ms 42360 KB Output is correct
5 Correct 30 ms 8952 KB Output is correct
6 Correct 421 ms 127480 KB Output is correct
7 Correct 433 ms 127480 KB Output is correct
8 Correct 425 ms 127480 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 8 ms 1024 KB Output is correct
3 Correct 562 ms 42380 KB Output is correct
4 Correct 571 ms 42360 KB Output is correct
5 Correct 30 ms 8952 KB Output is correct
6 Correct 421 ms 127480 KB Output is correct
7 Correct 433 ms 127480 KB Output is correct
8 Correct 425 ms 127480 KB Output is correct
9 Incorrect 5 ms 896 KB Output isn't correct
10 Halted 0 ms 0 KB -