답안 #65104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65104 2018-08-06T15:58:26 Z bazsi700 케이크 (CEOI14_cake) C++14
50 / 100
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;
                     ^~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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