oj.uz

Submission #977118

# Submission time Handle Problem Language Result Execution time Memory
977118 2024-05-07T12:01:43 Z alexdd Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 1000 ms 190476 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
set<pair<int,int>> init;
set<pair<int,pair<int,int>>> s;
set<pair<pair<int,int>,int>> s2;
signed main()
{
    cin>>n>>k;
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        int cv = 1000000LL*i;
        init.insert({cv,a});
        s.insert({a,{cv,cv}});
        s2.insert({{cv,cv},a});
    }
    while((int)s.size()>1)
    {
        pair<int,pair<int,int>> aux = *s.begin();
        int val = aux.first;
        int le = aux.second.first;
        int ri = aux.second.second;
        auto it = s2.lower_bound({{le,ri},val});
        if(next(it)!=s2.end() && (*next(it)).second==val)
        {
            int le2 = (*next(it)).first.first;
            int ri2 = (*next(it)).first.second;

            s.insert({val+1,{le,ri2}});
            s2.insert({{le,ri2},val+1});

            s.erase({val,{le2,ri2}});
            s2.erase({{le2,ri2},val});

            s.erase({val,{le,ri}});
            s2.erase({{le,ri},val});
        }
        else
        {
            k--;
            s.insert({val,{ri+1,ri+1}});
            s2.insert({{ri+1,ri+1},val});
            init.insert({ri+1,val});
        }
    }
    if(k<0)
    {
        while(1);
    }
    if(k>0)
    {
        int le = (*s.begin()).second.first;
        int ri = (*s.begin()).second.second;
        int val = (*s.begin()).first;
        if(k==1)
        {
            init.insert({ri+1,val});
        }
        else
        {
            while(1);
        }
    }
    for(auto x:init)
    {
        cout<<x.second<<" ";
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:55:13: warning: unused variable 'le' [-Wunused-variable]
   55 |         int le = (*s.begin()).second.first;
      |             ^~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 190280 KB Time limit exceeded
2 Execution timed out 1080 ms 190076 KB Time limit exceeded
3 Execution timed out 1070 ms 190100 KB Time limit exceeded
4 Execution timed out 1085 ms 190288 KB Time limit exceeded
5 Execution timed out 1076 ms 190476 KB Time limit exceeded
6 Execution timed out 1045 ms 190060 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 190160 KB Time limit exceeded
2 Execution timed out 1042 ms 189944 KB Time limit exceeded
3 Execution timed out 1046 ms 189756 KB Time limit exceeded
4 Execution timed out 1059 ms 190292 KB Time limit exceeded
5 Execution timed out 1072 ms 190220 KB Time limit exceeded
6 Execution timed out 1020 ms 190076 KB Time limit exceeded
7 Execution timed out 1079 ms 190296 KB Time limit exceeded
8 Execution timed out 1049 ms 190420 KB Time limit exceeded
9 Execution timed out 1026 ms 152240 KB Time limit exceeded
10 Execution timed out 1051 ms 57172 KB Time limit exceeded
11 Execution timed out 1074 ms 95180 KB Time limit exceeded
12 Execution timed out 1062 ms 348 KB Time limit exceeded
13 Execution timed out 1038 ms 344 KB Time limit exceeded
14 Execution timed out 1092 ms 344 KB Time limit exceeded