oj.uz

Submission #147948

# Submission time Handle Problem Language Result Execution time Memory
147948 2019-08-31T09:51:22 Z Dog River(#3676, evenharder) Get Hundred Points! (FXCUP4_hundred) C++17
33 / 100
 8 ms 384 KB 
#include "hundred.h"
using namespace std;
int root[100];
int col[100];
int get_root(int x)
{
    return root[x] = (root[x] == x ? x : get_root(root[x]));
}
int merge(int x, int y)
{
    x = get_root(x);
    y = get_root(y);
    if(x == y) return 0;
    root[x] = y;
    col[y] = max(col[x], col[y]);
    return 1;
}
std::string GetHundredPoints(int A, int B, int C) {
    string s = string(A, 'A') + string(B, 'B') + string(C, 'C');
    if (C)
    {
        return s;
    }
    for(int i=0;i<100;i++)
        root[i] = i;
    int x = Mark(s);
    if(B == 0) return string(100, 'A');
    else if(A == 0) return string(100, 'B');
    for(int i=0;i<B;i++)
    {
        int p = 0, q = 99-i;
        swap(s[p], s[q]);
        int y = Mark(s);
        if(y == x+2)
        {
            col[get_root(p)] = 'B';
            col[get_root(q)] = 'A';
        }
        else if(y == x-2)
        {   
            col[get_root(p)] = 'A';
            col[get_root(q)] = 'B';
        }
        else
        {
            merge(p, q);
        }
        swap(s[p], s[q]);
    }
    for(int i=1;i<A;i++)
    {
        int p = i, q = 99;
        swap(s[p], s[q]);
        int y = Mark(s);
        if(y == x+2)
        {
            col[get_root(p)] = 'B';
            col[get_root(q)] = 'A';
        }
        else if(y == x-2)
        {   
            col[get_root(p)] = 'A';
            col[get_root(q)] = 'B';
        }
        else
        {
            merge(p, q);
        }
        swap(s[p], s[q]);
    }
    for(int i=0;i<100;i++)
        s[i] = col[get_root(i)];
    return s;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 8 ms 256 KB Output is correct
4 Correct 7 ms 304 KB Output is correct
5 Correct 7 ms 384 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 8 ms 256 KB Output is correct
4 Correct 7 ms 304 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Incorrect 6 ms 256 KB Output isn't correct
7 Halted 0 ms 0 KB -