Submission #772089

#	Time	Username	Problem	Language	Result	Execution time	Memory
772089		HoriaHaivas	San (COCI17_san)	C++14	96 / 120	122 ms	65536 KiB

san

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
 
using namespace std;
 
struct cladire
{
    int h;
    int g;
    int poz;
};
 
struct subsir
{
    int sum;
    int highest;
};
 
cladire building[42];
vector<subsir> firsthalf;
int mars[42][(1<<20)+1];/// mars[i][j] = numarul de numere cu highest mai mic sau egal cu i in primele j numere din firsthalf
int n,k,i,j,val,ans,r,pas,ree;
 
bool cmp (cladire a, cladire b)
{
    return a.h<b.h;
}
 
bool cmp2(subsir a, subsir b)
{
    return a.sum<b.sum;
}
 
bool cmp3(cladire a, cladire b)
{
    return a.poz<b.poz;
}
 
void gen(int r)
{
    int mask,currsum,currhighest,j;
    bool ok;
    for (mask=0; mask<(1<<r); mask++)
    {
        ok=true;
        currsum=0;
        currhighest=-1;
        for (j=0; j<r && ok; j++)
        {
            if (mask&(1<<j))
            {
                if (building[j+1].h>=currhighest)
                {
                    currsum+=building[j+1].g;
                    currhighest=building[j+1].h;
                }
                else
                {
                    ok=false;
                }
            }
        }
        if (ok && currsum!=0)
        {
            if (currsum>=k)
                ans++;
            firsthalf.push_back({currsum,currhighest});
        }
    }
}
 
void gen2(int r)
{
    int mask,j,currsum,currhighest,currlowest;
    bool ok;
    for (mask=0; mask<(1<<r); mask++)
    {
        ok=true;
        currsum=0;
        currhighest=0;
        currlowest=n+1;
        for (j=0; j<r && ok; j++)
        {
            if (mask&(1<<j))
            {
                if (building[j+n/2+1].h>=currhighest)
                {
                    currsum+=building[j+n/2+1].g;
                    currhighest=building[j+n/2+1].h;
                    currlowest=min(currlowest,building[j+n/2+1].h);
                }
                else
                {
                    ok=false;
                }
            }
        }
        if (ok && currsum!=0)
        {
            ree=0;
            pas=(1<<20);
            while (pas)
            {
                if (ree+pas<firsthalf.size() && currsum+firsthalf[ree+pas].sum<k)
                    ree+=pas;
                pas=pas/2;
            }
            if (currsum+firsthalf[ree].sum<k)
                ree++;
            /*
            debugs(mask);
            debugs(currsum);
            debugs(currlowest);
            debugs(firsthalf[r].sum);
            debugs(r);
            debug(mars[currlowest][firsthalf.size()]-mars[currlowest][min(r-1,1LL*0)]);
            Doamne ajuta sa mearga (trebuia cu D mare)
            */
            if (ree!=0)
            ans+=mars[currlowest][firsthalf.size()-1]-mars[currlowest][ree-1];
            else
            ans+=mars[currlowest][firsthalf.size()-1];
            if (currsum>=k)
                ans++;
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (i=1; i<=n; i++)
    {
        cin >> building[i].h >> building[i].g;
        building[i].poz=i;
    }
    sort(building+1,building+1+n,cmp);
    val=0;
    for (i=1; i<=n; i++)
    {
        if (i==1 || building[i].h!=building[i-1].h)
            val++;
        building[i].h=val;
    }
    sort(building+1,building+1+n,cmp3);
    ans=0;
    gen(n/2);
    sort(firsthalf.begin(),firsthalf.end(),cmp2);
    for (i=0; i<firsthalf.size(); i++)
    {
        mars[firsthalf[i].highest][i]++;
        for (j=1; j<=n; j++)
        {
            mars[j][i]+=mars[j-1][i];
        }
        for (j=1;j<=n;j++)
        {
            mars[j][i]+=mars[j][i-1];
        }
    }
    if (n%2==0)
    gen2(n/2);
  	else
    gen2(n/2+1);
    cout << ans;
}

Compilation message (stderr)

san.cpp: In function 'void gen2(long long int)':
san.cpp:111:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                 if (ree+pas<firsthalf.size() && currsum+firsthalf[ree+pas].sum<k)
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:159:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subsir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (i=0; i<firsthalf.size(); i++)
      |               ~^~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 0 / 24