Submission #147678

#	Time	Username	Problem	Language	Result	Execution time	Memory
147678		함수컵 최고~ (#201)	Get Hundred Points! (FXCUP4_hundred)	C++17	100 / 100	9 ms	464 KiB

hundred

#include "hundred.h"
#include <bits/stdc++.h>

using namespace std;

int ans[110];
int sco[110];
int pos[110][3][3];
string his[110];

int good(int ans[]) {
    for (int i=0;i<100;i++) {
        int c = 0;
        for (int j=0;j<100;j++) {
            c += (his[i][j]==ans[j]+'A');
        }
        if (c!=sco[i]) return 0;
    }
    return 1;
}

std::string GetHundredPoints(int A, int B, int C) {
    int ch = -1;
    if (A==100) ch = 'A';
    else if (B==100) ch ='B';
    else if (C==100) ch = 'C';
    if (~ch) {
        string s;
        for (int i=0;i<100; i++) s.push_back(ch);
        return s;
    }
    int num[] = {A,B,C}, rev = 0;
    if (!A) {
        num[0]=B;
        num[1]=C;
        num[2]=A;
        rev = 1;
    }
    string que;
    for (int i=0;i<3;i++) {
        for (int j=0;j<num[i];j++) que.push_back('A'+(i+rev)%3);
    }
    int base = Mark(que);
    sco[0] = base;
    his[0] = que;
    for (int i=num[0];i<100;i++) {
        swap(que[0],que[i]);
        his[i] = que;
        int m = Mark(que);
        for (int j=0;j<3;j++) {
            for (int k=0;k<3;k++) {
                int val = (int)(j+'A'==que[0])+(int)(k+'A'==que[i])-(int)(j+'A'==que[i])-(int)(k+'A'==que[0]);
                if (val==m-base) {
                    pos[i][j][k] = 1;
                }
            }
        }
        sco[i] = m;
        swap(que[0],que[i]);
    }
    for (int i=1;i<num[0];i++){
        swap(que[i],que[num[0]]);
        his[i] = que;
        int m = Mark(que);
        for (int j=0;j<3;j++) {
            for (int k=0;k<3;k++) {
                int val = (int)(j+'A'==que[i])+(int)(k+'A'==que[num[0]])-(int)(j+'A'==que[num[0]])-(int)(k+'A'==que[i]);
                if (val==m-base) {
                    pos[i][j][k] = 1;
                }
            }
        }
        sco[i] = m;
        swap(que[i],que[num[0]]);
    }
    int gpos[] = {1,1,1};
    for (int c=0;c<3;c++) {
        ans[0] = c;
        for (int i=num[0];i<100;i++){
            int p = -1;
            for (int j=0;j<3;j++) {
                if (pos[i][c][j]) {
                    p=j;
                    break;
                }
            }
            if (p<0) {
                gpos[c] = 0;
                break;
            }
            ans[i] = p;
        }
        if (!gpos[c]) continue;
        for (int i=1;i<num[0];i++) {
            int p = -1;
            for (int j=0;j<3;j++) {
                if (pos[i][j][ans[num[0]]]) {
                    p=j;
                    break;
                }
            }
            if (p<0) {
                gpos[c] = 0;
                break;
            }
            ans[i] = p;
        }
        if (!gpos[c]) continue;
        if (good(ans)) {
            string tmp;
            for (int i=0;i<100;i++) tmp.push_back(ans[i]+'A');
            return tmp;
        }
    }

    return string();
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67