oj.uz

Submission #394272

# Submission time Handle Problem Language Result Execution time Memory
394272 2021-04-26T10:13:49 Z iulia13 Lollipop (POI11_liz) C++17
82 / 100
 2000 ms 38176 KB 
#include <iostream>

using namespace std;
///nu ai format x, dar ai format x-1=> pot x + 1
///ai format x si ai 1 langa dar n ai format x-1 => ?
///NU ai format x + 1 => NU ai 1[x-1]1 sau [x-1]2 => nu ai format x-1?????? sau e izolat la un capat 1[x-1] aaaa poti sa faci cu sufix ca sa scapi
///OK deci ca sa fie posibil sa ai x-1 tb sa ai x+1; iei sufix/prefix separat
///ai x + 1 => ca sa ai x- 1 tb sa ai un 1[x-1]1 sau [x-1]2 pai cam ai mereu
const int nmax = 2e6 + 5;
struct ura{
    int x, y;
};
ura sol[nmax];
int v[nmax];
char car[nmax];
int main()
{
    int n, q, i, s = 0;
    cin >> n >> q;
    cin >> car + 1;
    for (i = 1; i <= n; i++)
    {
        if (car[i] == 'T')
            v[i] = 2;
        else
            v[i] = 1;
        sol[v[i]] = {i, i};
        s += v[i];
        sol[s] = {1, i};
    }
    s = 0;
    for (i = n; i; i--)
    {
        s += v[i];
        sol[s] = {i, n};
    }
    for (i = 2 * n; i; i--)
    {
        if (sol[i].x)
            continue;
        if (!sol[i + 2].x)
            continue;
        int x = sol[i + 2].x;
        int y = sol[i + 2].y;
        if (v[x] == 2)
            sol[i] = {x + 1, y};
        else
        if (v[y] == 2)
            sol[i] = {x, y - 1};
        else
            sol[i] = {x + 1, y - 1};
    }
    while(q--)
    {
        cin >> i;
        if (!sol[i].x)
            cout << "NIE";
        else
            cout << sol[i].x << " " << sol[i].y;
        cout << '\n';
    }
    return 0;
}

Compilation message

liz.cpp: In function 'int main()':
liz.cpp:20:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     cin >> car + 1;
      |            ~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 42 ms 580 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 460 KB Output is correct
2 Correct 22 ms 592 KB Output is correct
3 Correct 25 ms 560 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1040 KB Output is correct
2 Correct 44 ms 908 KB Output is correct
3 Correct 209 ms 2424 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 2584 KB Output is correct
2 Correct 835 ms 7812 KB Output is correct
3 Correct 424 ms 4916 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2860 KB Output is correct
2 Correct 215 ms 2640 KB Output is correct
3 Correct 426 ms 5248 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 7620 KB Output is correct
2 Correct 667 ms 6848 KB Output is correct
3 Correct 865 ms 10212 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 17752 KB Output is correct
2 Correct 1325 ms 17056 KB Output is correct
3 Correct 1546 ms 21712 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 19788 KB Output is correct
2 Correct 1574 ms 22432 KB Output is correct
3 Correct 1797 ms 27060 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 37736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 38176 KB Time limit exceeded
2 Halted 0 ms 0 KB -