oj.uz

Submission #149142

# Submission time Handle Problem Language Result Execution time Memory
149142 2019-09-01T05:49:19 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 153596 KB 
#include "squad.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int nmax=300005;
const int magic=39;
typedef double ldouble;
struct line
{
    int 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;
}
ldouble a1,a2,b1,b2;
int lg[nmax];
ldouble 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(ldouble 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];
    ldouble r1,r2;
    int p1,p2;
    void ini(int B,int what)
    {
        int sum=0;
        for(i=0;i<n;i++)
        {
            wh[i]=(((i&(1<<B))!=0)^what);
            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/2,it%2);
}
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:115:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it=0;it<magic;it++)
     ^~~
squad.cpp:117: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 5 ms 1280 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 821 ms 64208 KB Output is correct
4 Correct 814 ms 64120 KB Output is correct
5 Correct 40 ms 11256 KB Output is correct
6 Correct 530 ms 153336 KB Output is correct
7 Correct 541 ms 153596 KB Output is correct
8 Correct 542 ms 153592 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 19 ms 1792 KB Output is correct
3 Correct 1510 ms 65460 KB Output is correct
4 Correct 1550 ms 65340 KB Output is correct
5 Correct 165 ms 5992 KB Output is correct
6 Execution timed out 3103 ms 108920 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 821 ms 64208 KB Output is correct
4 Correct 814 ms 64120 KB Output is correct
5 Correct 40 ms 11256 KB Output is correct
6 Correct 530 ms 153336 KB Output is correct
7 Correct 541 ms 153596 KB Output is correct
8 Correct 542 ms 153592 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 19 ms 1792 KB Output is correct
11 Correct 1510 ms 65460 KB Output is correct
12 Correct 1550 ms 65340 KB Output is correct
13 Correct 165 ms 5992 KB Output is correct
14 Execution timed out 3103 ms 108920 KB Time limit exceeded
15 Halted 0 ms 0 KB -