oj.uz

Submission #950009

# Submission time Handle Problem Language Result Execution time Memory
950009 2024-03-20T03:25:04 Z De3b0o Chorus (JOI23_chorus) C++14
0 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*n)
#define rc (2*n+1)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x%y);
}

string tb(ll x)
{
    string s = "";
    while(x>0)
    {
        if(x&1)
            s+='1';
        else
            s+='0';
        x/=2;
    }
    while(s.size()<60)
        s+='0';
    return s;
}

ll fb(string s)
{
    ll x = 0;
    ll c = 1;
    for(int8_t i = 0 ; 60>i ; i++)
    {
        if(s[i]=='1')
            x+=c;
        c*=2;
    }
    return x;
}

ll n , k;
string s;

bool check(ll x)
{
    string t = s;
    set<ll> idx;
    for(int i = 0 ; 2*n>i ; i++)
        if(s[i]=='B')
            idx.in(i);
    ll x1 = x;
    ll y = 0;
    while(!idx.empty())
    {
        if(x1==0)
            break;
        ll f = y;
        ll c = 0;
        ll y1;
        while(!idx.empty())
        {
            auto it = idx.begin();
            ll ff = *it;
            if(x1>=(ff-f-1)*c)
            {
                x1-=(ff-f-1)*c;
                f=ff;
                c++;
                y1=*it+1;
                idx.erase(it);
                continue;
            }
            else
                break;
        }
        for(int i = y ; f>=i ; i++)
            t[i]='A';
        for(int i = f ; i>f-c ; i--)
            t[i]='B';
        ll z = f-c+1-y;
        z-=c;
        y=y1;
        while(z--&&!idx.empty())
        {
            auto it = idx.begin();
            y=*it+1;
            idx.erase(it);
        }
    }
    idx.clear();
    for(int i = 0 ; 2*n>i ; i++)
        if(t[i]=='B')
            idx.in(i);
    y = 0;
    bool vis[2*n]={0};
    ll p = 0;
    bool e = 0;
    for(int i = 0 ; 2*n>i ; i++)
    {
        if(vis[i])
            continue;
        if(t[i]=='A')
        {
            p++;
            continue;
        }
        if(t[i]=='B'&&p==0)
        {
            e=1;
            continue;
        }
        y++;
        while(p--)
        {
            auto it = idx.begin();
            vis[*it]=1;
            idx.erase(it);
        }
        p=0;
    }
    if(e||y>k)
        return 0;
    else
        return 1;
}

int main()
{
    //d3
    cin >> n >> k;
    cin >> s;
    ll l = 0 , r = n*n;
    ll ans;
    while(l<=r)
    {
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cans
}

Compilation message

chorus.cpp: In function 'bool check(long long int)':
chorus.cpp:115:17: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |         for(int i = y ; f>=i ; i++)
      |                 ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -