| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 101571 | 2019-03-19T04:34:33 Z | SomeoneUnknown | Cake (CEOI14_cake) | C++14 | 342 ms | 5084 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
ii mii(int b, int c){
return make_pair(b,c);
}
int main(){
int n, s;
scanf("%d %d", &n, &s);
int topten[12];
topten[0] = 0; //the legendary cake of NULL, found only at the end of the world.
for(int i = 0; i < 11; i++){
topten[i] = -1;
}
int iv[n+2];
for(int i = 1; i <= n; i++){
scanf("%d", &iv[i]);
if(n - iv[i] < 10){
topten[n-iv[i]+1]=i;
}
}
iv[0] = iv[n+1] = n+2;
vector<ii> lfunentropic;
vector<ii> rtunentropic;
lfunentropic.push_back(mii(s, -n-6));
rtunentropic.push_back(mii(s, -n-6));
int lp = s-1;
int rp = s+1;
if(n - iv[lp] < 10) lp = 0;
//printf("%d", n-iv[rp]);
if(n - iv[rp] < 10) rp = n+1;
int gp = -n-5;
while(lp > 0 || rp <= n){
//printf("HI");
if(iv[lp] > iv[rp]){
rtunentropic.push_back(mii(rp, gp)); //last value
gp++;
rp++;
if(n - iv[rp] < 10) rp = n+1;
}else{
lfunentropic.push_back(mii(lp, gp));
gp++;
lp++;
if(n - iv[lp] < 10) lp = 0;
}
}
int Q;
scanf("%d", &Q);
for(int q = 0; q < Q; q++){
char nl, cmd;
scanf("%c%c", &nl, &cmd);
int id;
scanf("%d", &id);
if(cmd == 'F'){
if(id == s){
printf("0\n");
}else if(id < s){
bool found = false;
for(int i = 1; i <= min(10, n); i++){
// printf("X: %d %d %d\n", topten[i], s, id);
if(topten[i] < s && topten[i] >= id){
int clsest = n+1;
for(int j = i; j > 0; j--){
if(topten[j] > s) clsest = min(clsest, topten[j]);
//if(topten[j] < s && topten[j] > id) clsest = n+1;
}
found = true;
printf("%d\n",clsest-id-1);
break;
}
}
if(!found){
int h = lfunentropic.size()-1;
int l = 0;
while(h-1>l){
int m = (h+l)/2;
if(lfunentropic[m].first >= id){
h = m;
}else{
l = m;
}
}
int h2 = rtunentropic.size();
int l2 = 0;
while(h2-1>l2){
int m = (h2+l2)/2;
if(rtunentropic[m].second > lfunentropic[h].second){
h2 = m;
}else{
l2 = m;
}
}
printf("%d\n", rtunentropic[l2].first - id);
}
}else{
bool found = false;
for(int i = 1; i <= min(10, n); i++){
//printf("X: %d %d %d\n", topten[i], s, id);
if(topten[i] > s && topten[i] <= id){
int clsest = 0;
for(int j = i; j > 0; j--){
if(topten[j] < s) clsest = max(clsest, topten[j]);
//if(topten[j] > s && topten[j] < id) clsest = 0;
}
found = true;
printf("%d\n", id-clsest-1);
break;
}
}
if(!found){
//printf("HI");
int h = rtunentropic.size()-1;
int l = 0;
while(h-1>l){
int m = (h+l)/2;
if(rtunentropic[m].first <= id){
h = m;
}else{
l = m;
}
}
int h2 = lfunentropic.size();
int l2 = 0;
while(h2-1>l2){
int m = (h2+l2)/2;
if(lfunentropic[m].second > lfunentropic[h].second){
h2 = m;
}else{
l2 = m;
}
}
printf("%d\n", id - lfunentropic[l2].first);
}
}
}else{
int newpos;
scanf("%d", &newpos);
bool found = false;
for(int i = newpos; i <= 10; i++){
if(topten[i] == id){
for(int j = i; j > newpos; j--){
topten[j] = topten[j-1];
}
topten[newpos] = id;
found = true;
}
}
if(!found){
//demote topten[10];
if(topten[10] > s){
int clsest = n+1;
for(int i = 1; i < 10; i++){
if(topten[i] > s) clsest = min(clsest, topten[i]);
}
if(clsest > topten[10]){
rtunentropic.push_back(mii(clsest-1, q));
}
}else if(topten[10] < s){
int clsest = 0;
for(int i = 1; i < 10; i++){
if(topten[i] < s) clsest = max(clsest, topten[i]);
}
if(clsest < topten[10]){
lfunentropic.push_back(mii(clsest+1, q));
}
}
if(id < s){
while(lfunentropic[lfunentropic.size()-2].first<=id){
lfunentropic.pop_back();
}
if(lfunentropic[lfunentropic.size()-2].first==id+1){
lfunentropic.pop_back();
}else{
lfunentropic.back().first=id+1;
}
}else if(id > s){
while(rtunentropic[rtunentropic.size()-2].first>=id){
rtunentropic.pop_back();
}
if(rtunentropic[rtunentropic.size()-2].first==id-1){
rtunentropic.pop_back();
}else{
rtunentropic.back().first=id-1;
}
}
for(int j = 10; j > newpos; j--){
topten[j] = topten[j-1];
}
topten[newpos] = id;
found = true;
}
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 384 KB | Output is correct |
| 2 | Runtime error | 6 ms | 640 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 210 ms | 824 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Correct | 137 ms | 504 KB | Output is correct |
| 3 | Runtime error | 285 ms | 816 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Correct | 130 ms | 384 KB | Output is correct |
| 5 | Runtime error | 179 ms | 732 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 171 ms | 888 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Incorrect | 198 ms | 480 KB | Output isn't correct |
| 8 | Correct | 139 ms | 384 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 55 ms | 1400 KB | Output isn't correct |
| 2 | Runtime error | 52 ms | 1784 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 | Correct | 66 ms | 1272 KB | Output is correct |
| 4 | Correct | 3 ms | 384 KB | Output is correct |
| 5 | Incorrect | 71 ms | 2276 KB | Output isn't correct |
| 6 | Incorrect | 89 ms | 3312 KB | Output isn't correct |
| 7 | Correct | 73 ms | 1788 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 23 ms | 768 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Incorrect | 24 ms | 384 KB | Output isn't correct |
| 3 | Runtime error | 44 ms | 1756 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 | Runtime error | 9 ms | 896 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 | Runtime error | 6 ms | 640 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 76 ms | 2292 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 88 ms | 1336 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Incorrect | 90 ms | 1052 KB | Output isn't correct |
| 9 | Incorrect | 342 ms | 3964 KB | Output isn't correct |
| 10 | Runtime error | 189 ms | 1656 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 | Runtime error | 208 ms | 2196 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 | Runtime error | 296 ms | 5084 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 | Incorrect | 200 ms | 3068 KB | Output isn't correct |