| Task: | Tunnels |
| Sender: | herkar |
| Submission time: | 2017-01-22 13:04:51 +0200 |
| Language: | C++ |
| Status: | READY |
| Result: | 0 |
| group | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | RUNTIME ERROR | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | WRONG ANSWER | 0.04 s | 1 | details |
| #2 | WRONG ANSWER | 0.03 s | 1 | details |
| #3 | WRONG ANSWER | 0.05 s | 1 | details |
| #4 | WRONG ANSWER | 0.04 s | 1 | details |
| #5 | WRONG ANSWER | 0.05 s | 1 | details |
| #6 | WRONG ANSWER | 0.04 s | 2 | details |
| #7 | WRONG ANSWER | 0.04 s | 2 | details |
| #8 | RUNTIME ERROR | 0.23 s | 2 | details |
| #9 | RUNTIME ERROR | 0.22 s | 2 | details |
| #10 | WRONG ANSWER | 0.05 s | 2 | details |
| #11 | RUNTIME ERROR | 0.28 s | 3 | details |
| #12 | WRONG ANSWER | 0.12 s | 3 | details |
| #13 | RUNTIME ERROR | 0.22 s | 3 | details |
| #14 | RUNTIME ERROR | 0.31 s | 3 | details |
| #15 | RUNTIME ERROR | 0.21 s | 3 | details |
Code
#include <functional>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < int(b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> int(a); )
#define trav(i,v) for(auto&i:v)
#define all(c) (c).begin(), (c).end()
#define sz(c) int((c).size())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
int main(){
cin.tie(0);
cin.sync_with_stdio(0);
int n,k;
cin >> n >> k;
vi v(n);
trav(i,v) cin >> i;
set<pii> S;
map<int,int> C;
function<void(int)> add = [&](int a){
if(C[a]++) return;
if(S.empty()){
S.insert({a,a});
return;
}
auto it = S.lower_bound({a,-1});
if(it == S.begin()){
if(it->first == a+1){
pii p = *it;
S.erase(it);
S.insert({a,p.second});
} else S.insert({a,a});
} else if(it == S.end()) {
--it;
if(it->second == a-1){
pii p = *it;
S.erase(it);
S.insert({p.first,a});
} else S.insert({a,a});
} else {
auto it2 = it--;
if(it->second == a-1 && it2->first == a+1){
pii p = {it->first,it2->second};
S.erase(it),S.erase(S.upper_bound({a,-1}));
S.insert(p);
} else if(it->second == a-1){
pii p = {it->first,a};
S.erase(it);
S.insert(p);
} else if(it2->first == a+1){
pii p = {a,it2->second};
S.erase(it2);
S.insert(p);
} else S.insert({a,a});
}
}, rem = [&](int a){
if(--C[a]) return;
auto it = --S.upper_bound({a,-1});
pii p = *it;
S.erase(it);
if(p.first == a){
if(p.first != p.second) S.insert({a+1,p.second});
} else if(p.second == a)
S.insert({p.first,a-1});
else
S.insert({p.first,a-1}),S.insert({a+1,p.second});
};
rep(i,0,k) add(v[i]);
rep(i,k,n+1){
pii p = *S.begin();
if(!p.first) cout << p.second+1 << " ";
else cout << p.first-1 << " ";
if(i < n)add(v[i]);
rem(v[i-k]);
}
cout << endl;
}Test details
Test 1
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| 10 20 4 5 6 4 5 1 5 9 ... |
| correct output |
|---|
| 11 |
| user output |
|---|
| (empty) |
Test 2
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| 10 10 7 3 5 2 9 7 1 5 ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 0 |
Test 3
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| 10 5 5 7 3 8 5 8 3 7 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 2 2 2 2 2 2 |
Test 4
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| 10 4 9 1 6 8 7 1 5 7 |
| correct output |
|---|
| 3 |
| user output |
|---|
| 0 0 0 0 0 2 1 |
Test 5
Group: 1
Verdict: WRONG ANSWER
| input |
|---|
| 10 2 10 6 2 1 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 5 1 0 2 1 1 1 1 1 |
Test 6
Group: 2
Verdict: WRONG ANSWER
| input |
|---|
| 100 200 24 40 25 6 36 93 92 90 ... |
| correct output |
|---|
| 97 |
| user output |
|---|
| (empty) |
Test 7
Group: 2
Verdict: WRONG ANSWER
| input |
|---|
| 100 100 98 37 91 37 60 92 46 27 ... |
| correct output |
|---|
| 60 |
| user output |
|---|
| 0 |
Test 8
Group: 2
Verdict: RUNTIME ERROR
| input |
|---|
| 100 50 74 95 53 72 69 85 14 13 ... |
| correct output |
|---|
| 34 |
| user output |
|---|
| (empty) |
Error:
*** Error in `input/code': free(): invalid pointer: 0x00007ffc290feed8 ***
Test 9
Group: 2
Verdict: RUNTIME ERROR
| input |
|---|
| 100 40 28 76 10 81 13 52 46 83 ... |
| correct output |
|---|
| 29 |
| user output |
|---|
| (empty) |
Error:
*** Error in `input/code': free(): invalid pointer: 0x00007ffeb040e9b8 ***
Test 10
Group: 2
Verdict: WRONG ANSWER
| input |
|---|
| 100 20 27 35 72 92 56 4 64 80 ... |
| correct output |
|---|
| 18 |
| user output |
|---|
| 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
Test 11
Group: 3
Verdict: RUNTIME ERROR
| input |
|---|
| 100000 200000 89244 59358 22943 56710 63331 89437 56581 38400 ... |
| correct output |
|---|
| 102510 |
| user output |
|---|
| (empty) |
Test 12
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100000 100000 21701 85599 61542 21474 38081 29362 46316 64038 ... |
| correct output |
|---|
| 60593 |
| user output |
|---|
| 1 |
Test 13
Group: 3
Verdict: RUNTIME ERROR
| input |
|---|
| 100000 50000 86469 4833 16351 35505 59315 33011 95464 16985 ... |
| correct output |
|---|
| 35933 |
| user output |
|---|
| 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
Error:
*** Error in `input/code': free(): invalid pointer: 0x00007ffd58f55548 ***
Test 14
Group: 3
Verdict: RUNTIME ERROR
| input |
|---|
| 100000 40000 5392 23534 63204 45619 74330 25925 59678 88427 ... |
| correct output |
|---|
| 30074 |
| user output |
|---|
| 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
Error:
*** Error in `input/code': free(): invalid pointer: 0x00007ffd7dccdc48 ***
Test 15
Group: 3
Verdict: RUNTIME ERROR
| input |
|---|
| 100000 20000 80156 16531 71753 77661 7028 33389 17168 646 ... |
| correct output |
|---|
| 16882 |
| user output |
|---|
| 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ... |