oj.uz

Submission #750252

# Submission time Handle Problem Language Result Execution time Memory
750252 2023-05-29T08:38:03 Z ammar124 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 465 ms 72896 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define int long long
using namespace std;
ll power(ll a, ll b) { ll ans = 1; while (b) { if (b % 2) ans *= a; a *= a; b /= 2; } return ans; }
int const maxin = 1e6+6;
ll const mod = 1e9+7;
int arr[maxin];
int a,b;
int meow = 0;
int cnt = 0;
int xx , yy;
int xc = 0 , yc = 0;
map<ll , ll>mp;
void pls_work(int num)
{
    int g = a+b - cnt;
    int g2 = 0,g3 = 0;
    for(int i=0;i<100;i++)
    {
        if(power(2 , i) > g)
            break;
        g2 = power(2,i);
        g3 = i;
    }
    xx = num - g3;
    yy = num - g3 - 1;
    yc = (g - g2)*2;
    xc = g - yc;
    cnt = a+b;
}
void solve(int l , int r , int num)
{
    if(cnt == a + b)
    {
        return;
    }
    int indx = (l+r)/2;
    if(meow == a)
    {
        pls_work(num);
        return;
    }
    if(num < arr[meow])
    {
        mp[indx] = num;
        return;
        cnt++;
    }
    if(num == arr[meow])
    {
        mp[indx] = num;
        meow++;
        cnt++;
        return;
    }
    solve(l , indx , num-1);
    solve(indx , r , num-1);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>a>>b;
    for(int i=0;i<a;i++)
    {
        cin>>arr[i];
    }
    solve(0 , 1e17+5 , 30);
    for(auto it : mp)
    {
        cout<<it.second<<" ";
    }
    for(int i=0;i<xc;i++)
    {
        cout<<xx<<" ";
    }
    for(int i=0;i<yc;i++)
    {
        cout<<yy<<" ";
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 72780 KB Output is correct
2 Correct 428 ms 72804 KB Output is correct
3 Correct 465 ms 72748 KB Output is correct
4 Correct 418 ms 72880 KB Output is correct
5 Correct 407 ms 72828 KB Output is correct
6 Correct 413 ms 72804 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 399 ms 72804 KB Expected EOF
2 Correct 428 ms 72740 KB Output is correct
3 Incorrect 380 ms 72856 KB Unexpected end of file - int32 expected
4 Incorrect 376 ms 72792 KB Expected EOF
5 Incorrect 379 ms 72740 KB Expected EOF
6 Incorrect 381 ms 72896 KB Expected EOF
7 Incorrect 375 ms 72832 KB Expected EOF
8 Incorrect 371 ms 72780 KB Expected EOF
9 Incorrect 363 ms 67532 KB Expected EOF
10 Incorrect 194 ms 32660 KB Expected EOF
11 Incorrect 267 ms 48352 KB Expected EOF
12 Incorrect 62 ms 4328 KB Expected EOF
13 Incorrect 62 ms 4212 KB Expected EOF
14 Incorrect 60 ms 4300 KB not a zalsequence