oj.uz

Submission #64200

# Submission time Handle Problem Language Result Execution time Memory
64200 2018-08-03T13:37:17 Z antimirage Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 653 ms 11528 KB 
#include <iostream>
#include <assert.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <string.h>
#include <random>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e6 + 5;

int type, tests, pref[2][N], n, mn[2], bal1, bal2, sum[2][N], bal;

char s[N], ans[N];

bool fl;

main()
{
    cin >> type >> tests;
    while (tests--)
    {
        bal = 0;
        fl = false;

        scanf("%s", s + 1);

        n = strlen(s + 1);

        for (int i = 1; i <= n; i++)
        {
            pref[0][i] = pref[1][i] = 0;
            sum[0][i] = sum[1][i] = 0;
            if ( s[i] == '(' )
            {
                pref[0][i] = 1, pref[1][i] = 1, ans[i] = 'G';
                bal += 2;
            }
            else
            {
                if (pref[0][i - 1] > pref[1][i - 1])
                    ans[i] = 'R', pref[0][i] = -1;
                else
                    ans[i] = 'B', pref[1][i] = -1;

                bal--;
            }
            pref[0][i] += pref[0][i - 1];
            pref[1][i] += pref[1][i - 1];
        }
        bal1 = pref[0][n];
        bal2 = pref[1][n];
        mn[0] = mn[1] = 1e9 + 7;
//            for (int i = 1; i <= n; i++)
//                cout << pref[0][i] << " ";
//
//            cout << endl;
//            for (int i = 1; i <= n; i++)
//                cout << pref[1][i] << " ";
//
//            cout << endl;

        for (int i = n; i >= 1; i--)
        {
            mn[0] = min( mn[0], pref[0][i] );
            mn[1] = min( mn[1], pref[1][i] );
            if ( ans[i] == 'R' && mn[1] > 0 )
            {
                sum[1][i] = -1;
                ans[i] = 'G';
                mn[1]--;
                bal2--;
            }
            if ( ans[i] == 'B' && mn[0] > 0)
            {
                sum[0][i] = -1;
                ans[i] = 'G';
                mn[0]--;
                bal1--;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            sum[0][i] += sum[0][i - 1];
            sum[1][i] += sum[1][i - 1];
            pref[0][i] += sum[0][i];
            pref[1][i] += sum[1][i];
        }
        mn[0] = mn[1] = 1e9 + 7;

        for (int i = n; i >= 1; i--)
        {
            mn[0] = min( mn[0], pref[0][i] );
            mn[1] = min( mn[1], pref[1][i] );
            if (s[i] == ')') continue;
            if (mn[0] > 0 && bal1 > bal2)
            {
                ans[i] = 'B';
                mn[0]--;
                bal1--;
            }
            else if (mn[1] > 0)
            {
                ans[i] = 'R';
                mn[1]--;
                bal2--;
            }
        }
        if (bal < 0 || bal > n)
            puts("impossible");
        else
        {
            for (int i = 1; i <= n; i++)
                printf("%c", ans[i]);
            printf("\n");
        }
    }
}

Compilation message

zalmoxis.cpp:31:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s + 1);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Expected integer, but "impossible" found
2 Incorrect 3 ms 484 KB Expected integer, but "impossible" found
3 Incorrect 2 ms 484 KB Expected integer, but "impossible" found
4 Incorrect 3 ms 484 KB Expected integer, but "impossible" found
5 Incorrect 3 ms 484 KB Expected integer, but "impossible" found
6 Incorrect 3 ms 548 KB Expected integer, but "impossible" found

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 572 KB Expected integer, but "impossible" found
2 Incorrect 2 ms 616 KB Expected integer, but "impossible" found
3 Incorrect 2 ms 708 KB Expected integer, but "impossible" found
4 Incorrect 2 ms 708 KB Expected integer, but "impossible" found
5 Incorrect 2 ms 708 KB Expected integer, but "impossible" found
6 Incorrect 2 ms 708 KB Expected integer, but "impossible" found
7 Incorrect 3 ms 708 KB Expected integer, but "impossible" found
8 Incorrect 3 ms 708 KB Expected integer, but "impossible" found
9 Incorrect 38 ms 2748 KB Expected integer, but "impossible" found
10 Incorrect 312 ms 8200 KB Expected integer, but "impossible" found
11 Incorrect 72 ms 8200 KB Expected integer, but "impossible" found
12 Incorrect 653 ms 11432 KB Expected integer, but "impossible" found
13 Incorrect 600 ms 11528 KB Expected integer, but "impossible" found
14 Incorrect 579 ms 11528 KB Expected integer, but "impossible" found