oj.uz

Submission #148849

# Submission time Handle Problem Language Result Execution time Memory
148849 2019-09-01T05:15:17 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 308860 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=300005;
const int magic=50;
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;
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=18; 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;
    }
};
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=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;
    }
    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;
    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:108:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it=0;it<magic;it++)
     ^~~
squad.cpp:110: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 1408 KB Output is correct
2 Correct 10 ms 1792 KB Output is correct
3 Correct 1186 ms 73976 KB Output is correct
4 Correct 1220 ms 74104 KB Output is correct
5 Correct 62 ms 21752 KB Output is correct
6 Correct 844 ms 308860 KB Output is correct
7 Correct 951 ms 308856 KB Output is correct
8 Correct 875 ms 308832 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1536 KB Output is correct
2 Correct 31 ms 2176 KB Output is correct
3 Correct 2865 ms 76340 KB Output is correct
4 Correct 2431 ms 76340 KB Output is correct
5 Correct 316 ms 9448 KB Output is correct
6 Execution timed out 3109 ms 191352 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 1408 KB Output is correct
2 Correct 10 ms 1792 KB Output is correct
3 Correct 1186 ms 73976 KB Output is correct
4 Correct 1220 ms 74104 KB Output is correct
5 Correct 62 ms 21752 KB Output is correct
6 Correct 844 ms 308860 KB Output is correct
7 Correct 951 ms 308856 KB Output is correct
8 Correct 875 ms 308832 KB Output is correct
9 Correct 7 ms 1536 KB Output is correct
10 Correct 31 ms 2176 KB Output is correct
11 Correct 2865 ms 76340 KB Output is correct
12 Correct 2431 ms 76340 KB Output is correct
13 Correct 316 ms 9448 KB Output is correct
14 Execution timed out 3109 ms 191352 KB Time limit exceeded
15 Halted 0 ms 0 KB -