oj.uz

Submission #470053

# Submission time Handle Problem Language Result Execution time Memory
470053 2021-09-02T19:12:15 Z MohamedAliSaidane Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 16408 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (int)(1e8)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ld pointdist(ld x, ld y, ld point) { return ((x-point)*(y-point))/abs(x-y); }
//ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
////////////******SOLUTION******\\\\\\\\\\\

const int MAX_N = 1e5 + 4;
int n;
vi A;
int a;
map<int,int> m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> a;
    A.assign(n+2,0);
    A[0] = MOD;
    A[n+1] = MOD+1;
    for(int i = 1; i <=n;  i ++)
        cin >> A[i];
    m[a] = 0;
    int l = a -1;
    int r = a +1;
    int h = 1;
    while(l != 0 || r != n + 1)
    {
        if(A[l] < A[r])
        {
            m[l] = h;
            l --;
        }
        else
        {
            m[r] = h;
            r ++ ;
        }
        h ++;
    }
    int q; cin >> q;
    while(q--)
    {
        char query; cin >> query;
        if(query == 'F')
        {
            int idx; cin >> idx;
            cout << m[idx] << '\n';
        }
        else
        {
            int idx; cin >> idx;
            int e; cin >> e;
            int rang = n - A[idx] + 1;
            A[idx] = n-e + 1;
            for(int i = 1; i <= n; i ++)
            {
                if(i == idx)
                    continue;
                int rnk = n - A[i] + 1;
                if(rnk <= e && rnk >  rang)
                {
                    A[i]--;
                }
            }
            l = a -1;
            r = a +1;
            h = 1;
            while(l != 0 || r != n + 1)
            {
                if(A[l] < A[r])
                {
                    m[l] = h;
                    l --;
                }
                else
                {
                    m[r] = h;
                    r ++ ;
                }
                h ++;
            }
        }
    }
}
/*
Identify problem diagram: Brute force, Greedy, Dynamic Programming, Divide and Conquer
Reformulate the problem into something more theoretical
!!!!! IMPLICIT GRAPH ??????
!!!!! PAY ATTENTION TO THE CONSTRAINTS: DP nD ? BF ? BITMASKING ?
!!!!! SOLVE THE SUBTASKS FIRST: IT'S TOTALLY OK NOT TO SOLVE THE PROBLEM ENTIRELY
Search for multiple approaches: select the seemingly optimal one
Remember that you're the king of CP
Change your approach
Imagine Corner cases before submitting
Don't spend too much time on the problem: move on !
*/

Compilation message

cake.cpp:26:1: warning: multi-line comment [-Wcomment]
   26 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 972 KB Time limit exceeded
2 Execution timed out 2082 ms 972 KB Time limit exceeded
3 Execution timed out 2077 ms 972 KB Time limit exceeded
4 Execution timed out 2083 ms 972 KB Time limit exceeded
5 Execution timed out 2083 ms 1868 KB Time limit exceeded
6 Execution timed out 2043 ms 1868 KB Time limit exceeded
7 Execution timed out 2082 ms 1868 KB Time limit exceeded
8 Execution timed out 2080 ms 1868 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 938 ms 7500 KB Output isn't correct
2 Incorrect 867 ms 7260 KB Output isn't correct
3 Incorrect 836 ms 7232 KB Output isn't correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1768 ms 16408 KB Output isn't correct
6 Execution timed out 2001 ms 16244 KB Time limit exceeded
7 Execution timed out 2069 ms 16088 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 976 KB Time limit exceeded
2 Execution timed out 2078 ms 1044 KB Time limit exceeded
3 Execution timed out 2070 ms 3396 KB Time limit exceeded
4 Execution timed out 2071 ms 3360 KB Time limit exceeded
5 Execution timed out 2075 ms 1376 KB Time limit exceeded
6 Execution timed out 2071 ms 4276 KB Time limit exceeded
7 Execution timed out 2068 ms 1176 KB Time limit exceeded
8 Execution timed out 2068 ms 6092 KB Time limit exceeded
9 Execution timed out 2071 ms 14788 KB Time limit exceeded
10 Execution timed out 2081 ms 1396 KB Time limit exceeded
11 Execution timed out 2071 ms 1704 KB Time limit exceeded
12 Execution timed out 2071 ms 11968 KB Time limit exceeded
13 Execution timed out 2077 ms 14724 KB Time limit exceeded