| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65104 |
2018-08-06T15:58:26 Z |
bazsi700 |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
8764 KB |
#include <bits/stdc++.h>
using namespace std;
struct Block {
bool L;
int prevblocksizesl;
int prevblocksizesr;
int siz;
vector<pair<int,int> > tops;
};
int arr[250005];
int ans[250005];
//14:45-19:45
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,A;
cin >> n >> A;
vector<pair<int,int> > tosort (n);
vector<int> smallranks;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
tosort[i-1] = {arr[i],i};
}
sort(tosort.begin(),tosort.end());
for(int i = n-1; i >= max(n-11,0); i--) {
smallranks.push_back(tosort[i].second);
}
int Q;
cin >> Q;
vector<pair<int,int> > quer(Q);
int fcn = 0;
int ecn = 0;
for(int i = 0; i < Q; i++) {
char ch;
cin >> ch;
if(ch == 'F') {
int pos;
cin >> pos;
quer[i] = {pos,-1};
fcn++;
} else {
int pos,ran;
cin >> pos >> ran;
quer[i] = {pos,ran};
ecn++;
}
}
if((n <= 10000 && Q <= 10000) || fcn <= 500) {
for(auto q : quer) {
if(q.second == -1) {
int pos = q.first;
if(pos == A) {
cout << "0\n";
continue;
}
int leftind = A-1;
int rightind = A+1;
for(int i = 1; i < n; i++) {
if(leftind == 0) {
if(rightind == pos) {
cout << i << "\n";
break;
}
rightind++;
continue;
}
if(rightind == n+1) {
if(leftind == pos) {
cout << i << "\n";
break;
}
leftind--;
continue;
}
if(arr[leftind] < arr[rightind]) {
if(leftind == pos) {
cout << i << "\n";
break;
}
leftind--;
continue;
} else {
if(rightind == pos) {
cout << i << "\n";
break;
}
rightind++;
continue;
}
}
} else {
int pos = q.first;
int ran = q.second;
bool cont = false;
for(int el : smallranks) {
if(el == pos) {
cont = true;
}
}
if(!cont) {
vector<int> nwv;
for(int i = 0; i < ran-1; i++) {
nwv.push_back(smallranks[i]);
}
nwv.push_back(pos);
for(int i = ran-1; i <= min(n-1,10); i++) {
nwv.push_back(smallranks[i]);
}
swap(nwv,smallranks);
} else {
vector<int> nwv;
for(int i = 0; i < ran-1; i++) {
nwv.push_back(smallranks[i]);
}
nwv.push_back(pos);
for(int i = ran-1; i <= min(n-1,10); i++) {
if(smallranks[i] != pos) {
nwv.push_back(smallranks[i]);
}
}
swap(nwv,smallranks);
}
int prv = -1;
for(int i = 0; i <= 10; i++) {
int el = smallranks[i];
if(el == pos) {
if(i != smallranks.size()-1) {
arr[el] = arr[smallranks[i+1]]+1;
} else {
arr[el] = arr[smallranks[i-1]]-1;
}
break;
}
arr[el]++;
}
/*for(int i = 1; i <= n; i++) {
cout << arr[i] << " ";
}
cout << endl;*/
}
}
} else {
int leftind = A-1;
int rightind = A+1;
for(int i = 1; i < n; i++) {
if(leftind == 0) {
ans[rightind] = i;
rightind++;
continue;
}
if(rightind == n+1) {
ans[leftind] = i;
leftind--;
continue;
}
if(arr[leftind] < arr[rightind]) {
ans[leftind] = i;
leftind--;
continue;
} else {
ans[rightind] = i;
rightind++;
continue;
}
}
for(auto q : quer) {
if(q.second == -1) {
int pos = q.first;
cout << ans[pos] << "\n";
} else {
int pos = q.first;
int ran = q.second;
bool cont = false;
for(int el : smallranks) {
if(el == pos) {
cont = true;
}
}
if(!cont) {
vector<int> nwv;
for(int i = 0; i < ran-1; i++) {
nwv.push_back(smallranks[i]);
}
nwv.push_back(pos);
for(int i = ran-1; i <= min(n-1,10); i++) {
nwv.push_back(smallranks[i]);
}
swap(nwv,smallranks);
} else {
vector<int> nwv;
for(int i = 0; i < ran-1; i++) {
nwv.push_back(smallranks[i]);
}
nwv.push_back(pos);
for(int i = ran-1; i <= min(n-1,10); i++) {
if(smallranks[i] != pos) {
nwv.push_back(smallranks[i]);
}
}
swap(nwv,smallranks);
}
int prv = -1;
for(int i = 0; i <= 10; i++) {
int el = smallranks[i];
if(el == pos) {
if(i != smallranks.size()-1) {
arr[el] = arr[smallranks[i+1]]+1;
} else {
arr[el] = arr[smallranks[i-1]]-1;
}
break;
}
arr[el]++;
}
leftind = A-1;
rightind = A+1;
for(int i = 1; i < n; i++) {
if(leftind == 0) {
ans[rightind] = i;
rightind++;
continue;
}
if(rightind == n+1) {
ans[leftind] = i;
leftind--;
continue;
}
if(arr[leftind] < arr[rightind]) {
ans[leftind] = i;
leftind--;
continue;
} else {
ans[rightind] = i;
rightind++;
continue;
}
}
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:133:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != smallranks.size()-1) {
~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:129:21: warning: unused variable 'prv' [-Wunused-variable]
int prv = -1;
^~~
cake.cpp:214:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != smallranks.size()-1) {
~~^~~~~~~~~~~~~~~~~~~~~~
cake.cpp:210:21: warning: unused variable 'prv' [-Wunused-variable]
int prv = -1;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
448 KB |
Output is correct |
| 3 |
Correct |
4 ms |
520 KB |
Output is correct |
| 4 |
Correct |
10 ms |
728 KB |
Output is correct |
| 5 |
Correct |
49 ms |
804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
392 ms |
4580 KB |
Output is correct |
| 2 |
Correct |
290 ms |
4620 KB |
Output is correct |
| 3 |
Correct |
323 ms |
4620 KB |
Output is correct |
| 4 |
Correct |
293 ms |
4708 KB |
Output is correct |
| 5 |
Correct |
339 ms |
4836 KB |
Output is correct |
| 6 |
Correct |
309 ms |
4836 KB |
Output is correct |
| 7 |
Correct |
345 ms |
4836 KB |
Output is correct |
| 8 |
Correct |
335 ms |
4836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
4836 KB |
Output is correct |
| 2 |
Correct |
71 ms |
4836 KB |
Output is correct |
| 3 |
Correct |
61 ms |
4836 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4836 KB |
Output is correct |
| 5 |
Correct |
139 ms |
6044 KB |
Output is correct |
| 6 |
Correct |
115 ms |
6044 KB |
Output is correct |
| 7 |
Correct |
118 ms |
6044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
6044 KB |
Output is correct |
| 2 |
Correct |
223 ms |
6044 KB |
Output is correct |
| 3 |
Execution timed out |
2045 ms |
6044 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2064 ms |
6044 KB |
Time limit exceeded |
| 5 |
Correct |
440 ms |
6044 KB |
Output is correct |
| 6 |
Execution timed out |
2068 ms |
6044 KB |
Time limit exceeded |
| 7 |
Correct |
1302 ms |
6044 KB |
Output is correct |
| 8 |
Execution timed out |
2058 ms |
6044 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2041 ms |
8672 KB |
Time limit exceeded |
| 10 |
Correct |
924 ms |
8672 KB |
Output is correct |
| 11 |
Execution timed out |
2036 ms |
8672 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2056 ms |
8672 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2061 ms |
8764 KB |
Time limit exceeded |
