oj.uz

Submission #149023

# Submission time Handle Problem Language Result Execution time Memory
149023 2019-09-01T05:35:29 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 145148 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=300005;
const int magic=22;
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 sum=0;
        for(i=0;i<n;i++)
        {
            wh[i]=gen()%2;
            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();
}

long long BestSquad(int X, int Y){
    long long ret=0;
    long double r1,r2;
    int p1,p2;
    p1=Aa.cb(r1/r2);
    p2=Dd.cb(r1/r2);
    if(p1!=p2)return (Aa.st[p1].ev(X,Y)+Dd.st[p2].ev(X,Y));
    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:118:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it=0;it<magic;it++)
     ^~~
squad.cpp:120:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return ret;
  ^~~~~~
squad.cpp:115:13: warning: 'r1' is used uninitialized in this function [-Wuninitialized]
     p1=Aa.cb(r1/r2);
        ~~~~~^~~~~~~
squad.cpp:115:13: warning: 'r2' is used uninitialized in this function [-Wuninitialized]

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 709 ms 45944 KB Output is correct
4 Correct 684 ms 45944 KB Output is correct
5 Correct 40 ms 10360 KB Output is correct
6 Correct 557 ms 145144 KB Output is correct
7 Correct 565 ms 145144 KB Output is correct
8 Correct 604 ms 145148 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 896 KB Output is correct
2 Correct 16 ms 1280 KB Output is correct
3 Correct 1401 ms 46136 KB Output is correct
4 Correct 1382 ms 46140 KB Output is correct
5 Correct 121 ms 4968 KB Output is correct
6 Execution timed out 3103 ms 93432 KB Time limit exceeded
7 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 709 ms 45944 KB Output is correct
4 Correct 684 ms 45944 KB Output is correct
5 Correct 40 ms 10360 KB Output is correct
6 Correct 557 ms 145144 KB Output is correct
7 Correct 565 ms 145144 KB Output is correct
8 Correct 604 ms 145148 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 16 ms 1280 KB Output is correct
11 Correct 1401 ms 46136 KB Output is correct
12 Correct 1382 ms 46140 KB Output is correct
13 Correct 121 ms 4968 KB Output is correct
14 Execution timed out 3103 ms 93432 KB Time limit exceeded
15 Halted 0 ms 0 KB -