Task: | Key cutting |
Sender: | ä |
Submission time: | 2024-11-16 14:40:01 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | WRONG ANSWER | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | WRONG ANSWER | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | WRONG ANSWER | 0.00 s | details |
#7 | WRONG ANSWER | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | WRONG ANSWER | 0.03 s | details |
#10 | WRONG ANSWER | 0.03 s | details |
#11 | WRONG ANSWER | 0.03 s | details |
#12 | WRONG ANSWER | 0.03 s | details |
#13 | WRONG ANSWER | 0.04 s | details |
#14 | WRONG ANSWER | 0.04 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:45:18: warning: unused variable 'ok' [-Wunused-variable] 45 | bool ok = true; | ^~ input/code.cpp:47:17: warning: unused variable 'mi2' [-Wunused-variable] 47 | int mi2 = 1000000001; | ^~~
Code
#include <bits/stdc++.h> // g++ -std=c++17 k.cpp -o k using namespace std; int s[10101010]; int n; unordered_map<int, int> lahin; int hae(int a, int b){ a +=n; b+=n; int mi = 1000000001; while(a<=b){ if(a%2==1) mi = min(mi, s[a++]); if(a%2==0) mi = min(mi, s[b--]); a/=2; b/=2; } return mi; } void add(int k, int x){ k+=n; s[k]=x; for (k /=2; k>=1; k/=2){ s[k] = min(s[k*2], s[k*2+1]); } } int main() { cin >> n; for (int i = 0; i < n;++i){ int oof; cin >> oof; add(i, oof); } unordered_set<int> f; int cuts = 0; for (int i = 0; i < n; ++i){ auto coun = lahin.count(s[i+n]); //cout << "etsitaaan " << s[i+n] << " " << coun << endl; if (coun==0){ //cout << "ei loyd " << i << " " << s[i+n] << endl; cuts += 1; lahin[s[i+n]] = i; } else { auto lah = lahin[s[i+n]]; bool ok = true; int mi = hae(lah+1, i); int mi2 = 1000000001; //for (int j = i-1; j > lah; --j){ // mi2 = min(mi2, s[j+n]); //} ///cout << "loyd " << mi << " " << s[i+n] << endl; if (mi < s[i+n]){ //cout << "lis 1" << endl; cuts += 1; } lahin[s[i+n]] = i; } } cout << cuts << endl; return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
3 1 2 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 2
Verdict: WRONG ANSWER
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
1 |
Test 3
Verdict: ACCEPTED
input |
---|
1 9 |
correct output |
---|
1 |
user output |
---|
1 |
Test 4
Verdict: WRONG ANSWER
input |
---|
100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
0 |
user output |
---|
1 |
Test 5
Verdict: WRONG ANSWER
input |
---|
100 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ... |
correct output |
---|
25 |
user output |
---|
26 |
Test 6
Verdict: WRONG ANSWER
input |
---|
100 2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ... |
correct output |
---|
41 |
user output |
---|
42 |
Test 7
Verdict: WRONG ANSWER
input |
---|
100 36 5 10 37 94 59 20 31 64 2 58... |
correct output |
---|
99 |
user output |
---|
100 |
Test 8
Verdict: ACCEPTED
input |
---|
100 228768416 32415139 952687252 6... |
correct output |
---|
100 |
user output |
---|
100 |
Test 9
Verdict: WRONG ANSWER
input |
---|
100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
0 |
user output |
---|
1 |
Test 10
Verdict: WRONG ANSWER
input |
---|
100000 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ... |
correct output |
---|
24965 |
user output |
---|
24966 |
Test 11
Verdict: WRONG ANSWER
input |
---|
100000 2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ... |
correct output |
---|
38968 |
user output |
---|
38969 |
Test 12
Verdict: WRONG ANSWER
input |
---|
100000 4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ... |
correct output |
---|
59156 |
user output |
---|
59157 |
Test 13
Verdict: WRONG ANSWER
input |
---|
100000 18 5 6 16 8 10 1 7 4 15 5 9 19... |
correct output |
---|
82598 |
user output |
---|
82599 |
Test 14
Verdict: WRONG ANSWER
input |
---|
100000 33 37 37 86 42 38 18 10 77 57 ... |
correct output |
---|
94897 |
user output |
---|
94898 |