oj.uz

Submission #148970

# Submission time Handle Problem Language Result Execution time Memory
148970 2019-09-01T05:29:00 Z Dopatii(#3751, bogdan10bos, Gioto, Bodo171) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 1243 ms 133368 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=300005;
const int magic=20;
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;
    }
};
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;
    }
    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:111:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it=0;it<magic;it++)
     ^~~
squad.cpp:113: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 896 KB Output is correct
3 Correct 683 ms 39416 KB Output is correct
4 Correct 686 ms 39416 KB Output is correct
5 Correct 39 ms 9464 KB Output is correct
6 Correct 550 ms 133368 KB Output is correct
7 Correct 523 ms 133368 KB Output is correct
8 Correct 510 ms 133368 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 17 ms 1144 KB Output is correct
3 Correct 1161 ms 41780 KB Output is correct
4 Correct 1243 ms 41780 KB Output is correct
5 Incorrect 105 ms 4328 KB Output isn't correct
6 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 896 KB Output is correct
3 Correct 683 ms 39416 KB Output is correct
4 Correct 686 ms 39416 KB Output is correct
5 Correct 39 ms 9464 KB Output is correct
6 Correct 550 ms 133368 KB Output is correct
7 Correct 523 ms 133368 KB Output is correct
8 Correct 510 ms 133368 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 17 ms 1144 KB Output is correct
11 Correct 1161 ms 41780 KB Output is correct
12 Correct 1243 ms 41780 KB Output is correct
13 Incorrect 105 ms 4328 KB Output isn't correct
14 Halted 0 ms 0 KB -