oj.uz

Submission #676575

# Submission time Handle Problem Language Result Execution time Memory
676575 2022-12-31T10:33:45 Z vjudge1 Cake (CEOI14_cake) C++17
35 / 100
 2000 ms 22620 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl "\n"
const int mod = (int) 1e9+7;
const int N=2e5+5;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n,a; cin>>n>>a;
    int d[n+5],opd[n+5];
    for (int i=1;i<=n;i++) {
      cin>>d[i];
      opd[d[i]]=i;
    }

    int when[n+5];
    when[a]=0;
    int l=a-1,r=a+1,time=1;
    while (time<n) {
      if (l>=1  && ((r>n) || (r<=n && d[l]<d[r]))) {
        when[l]=time; time++; l--;
      }
      if (r<=n && ((l<1) || (l>=1 && d[r]<d[l]))) {
        when[r]=time; time++; r++;
      }
    }

    vector<pair<int,pair<int,int> > >tst;

    int f=0,e=0;
    int q; cin>>q;
    while (q--) {
      char c; cin>>c;
      if (c=='F') {
        f++;
        int x; cin>>x;
        tst.push_back({1,{x,0}});
      }
      else {
        e++;
        int x,nw; cin>>x>>nw;
        tst.push_back({2,{x,nw}});
      }
    }

    int lste=-1;
    for (int qq=0;qq<tst.size();qq++) {
      int x=tst[qq].second.first;
      if (tst[qq].first==1) {
        if (e>100 && lste==-1) {
          int l=a-1,r=a+1,time=1;
          while (time<n) {
            if (l>=1  && ((r>n) || (r<=n && d[l]<d[r]))) {
              when[l]=time; time++; l--;
            }
            if (r<=n && ((l<1) || (l>=1 && d[r]<d[l]))) {
              when[r]=time; time++; r++;
            }
          }
        }
        cout<<when[x]<<endl;
        lste=1;
      }
      else {
        lste=-1;
        int nw=tst[qq].second.second;
        nw=n-(nw-1);
        for (int i=d[x]+1;i<=nw;i++) {
          d[opd[i]]--; opd[d[opd[i]]]=opd[i];
        }
        d[x]=nw;
        opd[d[x]]=x;

        if (e<=100) {
          int l=a-1,r=a+1,time=1;
          while (time<n) {
            if (l>=1  && ((r>n) || (r<=n && d[l]<d[r]))) {
              when[l]=time; time++; l--;
            }
            if (r<=n && ((l<1) || (l>=1 && d[r]<d[l]))) {
              when[r]=time; time++; r++;
            }
          }
        }
      }

    }

}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:49:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int qq=0;qq<tst.size();qq++) {
      |                   ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 183 ms 1044 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 15196 KB Time limit exceeded
2 Correct 335 ms 14816 KB Output is correct
3 Execution timed out 2058 ms 15360 KB Time limit exceeded
4 Correct 83 ms 14624 KB Output is correct
5 Execution timed out 2049 ms 16604 KB Time limit exceeded
6 Execution timed out 2064 ms 16724 KB Time limit exceeded
7 Execution timed out 2076 ms 16812 KB Time limit exceeded
8 Correct 104 ms 16704 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 5772 KB Output is correct
2 Correct 49 ms 5808 KB Output is correct
3 Correct 40 ms 5832 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 224 ms 9464 KB Output is correct
6 Correct 163 ms 9280 KB Output is correct
7 Correct 64 ms 9288 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 1996 KB Output is correct
2 Correct 485 ms 1996 KB Output is correct
3 Execution timed out 2081 ms 4936 KB Time limit exceeded
4 Execution timed out 2068 ms 4808 KB Time limit exceeded
5 Correct 504 ms 6584 KB Output is correct
6 Execution timed out 2077 ms 9228 KB Time limit exceeded
7 Execution timed out 2072 ms 7076 KB Time limit exceeded
8 Execution timed out 2072 ms 10052 KB Time limit exceeded
9 Execution timed out 2064 ms 22564 KB Time limit exceeded
10 Correct 1608 ms 13376 KB Output is correct
11 Execution timed out 2077 ms 16568 KB Time limit exceeded
12 Execution timed out 2069 ms 21260 KB Time limit exceeded
13 Execution timed out 2086 ms 22620 KB Time limit exceeded