Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 15:37:38
2018-05-26 14:47:44
Task:Coins
Sender:HIIT AND RUN
Submission time:2018-05-26 15:37:38
Language:C++
Status:READY
Result:WRONG ANSWER

Test results

testverdicttime (s)
#1WRONG ANSWER0.67 / 1.00details
#2ACCEPTED0.45 / 1.00details
#3ACCEPTED0.43 / 1.00details
#4ACCEPTED0.44 / 1.00details
#5WRONG ANSWER0.61 / 1.00details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:62:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (isojaMatchaavia >= from->size()) ans.push_back(to == &r ? "<" : ">");
             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Code


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    
    set<ll> l;
    set<ll> r;
    
    vector<ll> backtrackActions;
    
    for (int i=0; i< n; i++) {
        ll coin;
        cin >> coin;
        ll leftOrRight;
        cin >> leftOrRight;
        
        backtrackActions.push_back(coin);
        backtrackActions.push_back(leftOrRight);
        
        if (leftOrRight == 1) l.insert(coin);
        else r.insert(coin);
    }
    
    
    
    auto to = &r;
    auto from = &l;
    
    if (!l.empty()) {
        if (r.empty() || *l.rbegin() > *r.rbegin()) {
            to = &l;
            from = &r;
            
            
        }
        
    }
    
    ll largest = *to->rbegin();
    
    
    vector<string> ans;
    set<ll> pq;
    
    ll countRemovedSmalls = 0;
    ll i = backtrackActions.size() -1;
    
    while (true) {
        ll smallestInFrom = (from->empty() ? 0 : *from->begin());
        
        //cout << "largest" << largest << "smallest" << smallestInFrom << endl;
        //cout << "from" << from->size() << endl;
        ll countSmallerThanFromSmallest = max((ll) 0, smallestInFrom - 1 - countRemovedSmalls);
        ll isojaMatchaavia = to->size() - countSmallerThanFromSmallest;
        //cout << "isoja" << isojaMatchaavia << endl;
        
        if (isojaMatchaavia >= from->size()) ans.push_back(to == &r ? "<" : ">");
        else ans.push_back("?");

        
        if (i <= 2) break;
        ll leftOrRight = backtrackActions[i--];
        ll coin = backtrackActions[i--];
        
        
        if (coin < smallestInFrom) {
                to->erase(coin);
                countRemovedSmalls++;
        } else if (coin == smallestInFrom) {
                from->erase(coin);
                countRemovedSmalls++;
                ll newSmallest = (from->empty() ? 0 : *from->begin());
                while (!pq.empty() && *pq.begin() < newSmallest) {
                        pq.erase(pq.begin());
                        countRemovedSmalls++;
                }
        } else if (coin == largest) {
                to->erase(coin);
                largest = (to->empty() ? -1 : *to->rbegin());
                //System.out.println("largest " + largest);
                if (largest == -1 || (!from->empty() && *from->rbegin() > largest)) {
                        // swap to and from
                        auto helper = to;
                        to = from;
                        from = helper;
                        largest = *to->rbegin();
                }
                pq.insert(coin);
        } else {
                if (leftOrRight == 2) r.erase(coin);
                else l.erase(coin);
                pq.insert(coin);
        }
    }
        for (int i=ans.size()-1; i >= 0; i--) {
            cout << ans[i] << endl;
            
        }
    
}

Test details

Test 1

Verdict: WRONG ANSWER

input
200000
175878 1
146174 1
4939 2
181388 1
27963 2
28393 1
101955 2
129380 1
53446 1
56883 2
41641 2
52574 1
185690 2
17672 2
187 2
29223 1
116434 2
81263 2
153912 2
...
view   save

correct output
>
>
>
>
>
>
>
>
>
>
>
>
?
?
?
?
?
?
?
?
...
view   save

user output
>
>
>
>
>
>
>
>
>
>
>
>
<
<
<
<
<
<
<
<
...
view   save

Test 2

Verdict: ACCEPTED

input
200000
1 2
2 1
3 2
4 1
5 2
6 1
7 2
8 1
9 2
10 1
11 2
12 1
13 2
14 1
15 2
16 1
17 2
18 1
19 2
...
view   save

correct output
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
...
view   save

user output
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
<
>
...
view   save

Test 3

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
5 1
6 2
7 2
8 2
9 2
10 2
11 1
12 1
13 1
14 1
15 1
16 2
17 2
18 2
19 2
...
view   save

correct output
>
>
>
>
>
?
?
?
?
<
?
?
?
?
>
?
?
?
?
<
...
view   save

user output
>
>
>
>
>
?
?
?
?
<
?
?
?
?
>
?
?
?
?
<
...
view   save

Test 4

Verdict: ACCEPTED

input
200000
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
...
view   save

correct output
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
...
view   save

user output
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
...
view   save

Test 5

Verdict: WRONG ANSWER

input
200000
188909 2
58944 1
26824 1
143263 2
108129 2
170746 1
129857 2
151652 1
92616 1
5122 1
85017 2
133713 2
130510 1
23167 2
55879 2
81852 1
117028 1
185678 1
5335 2
...
view   save

correct output
<
<
?
<
<
<
<
?
?
?
?
?
?
?
?
?
?
?
?
?
...
view   save

user output
<
<
?
<
<
<
<
<
?
?
?
<
?
<
<
<
?
?
?
<
...
view   save