제출 #1339041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1339041		alexdd	Conference (JOI25_conference)	C++20	0 / 100	2094 ms	3024 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<int> v[3][3];

int solve_dominant(vector<int> cnt, int d)
{
    int A = -1, B = -1;
    for(int i=0;i<3;i++)
    {
        if(i != d)
        {
            if(A == -1)
                A = i;
            else
                B = i;
        }
    }
    assert(A != -1 && B != -1);

    int base = 0;
    for(int i=0;i<3;i++)
        for(int j=i+1;j<3;j++)
            base += v[i][j].size();

    base += 1 * v[A][B].size();
    base += 2 * v[A][A].size();
    base += 2 * v[B][B].size();

    int rez = INF;
    for(int cntAA=0;cntAA<=v[A][A].size();cntAA++)
    {
        int aux = base;
        int ramasA = cnt[A];
        for(int i=0;i<cntAA;i++)
        {
            ramasA -= v[A][A][i];
            aux -= 2;
        }

        if(ramasA < 0)
            continue;

        vector<int> newAB;
        for(int i=0;i<v[A][B].size();i++)
        {
            if(ramasA >= v[A][B][i])
            {
                ramasA -= v[A][B][i];
                aux -= 1;
            }
            else
            {
                newAB.push_back(v[A][B][i] - ramasA);
                ramasA = 0;
            }
        }

        for(int cntBB=0;cntBB<=v[B][B].size();cntBB--)
        {
            int ramasB = cnt[B], myaux = aux;
            for(int i=0;i<cntBB;i++)
            {
                ramasB -= v[B][B][i];
                myaux -= 2;
            }
            if(ramasB < 0)
                continue;
            for(int i=0;i<newAB.size();i++)
            {
                if(ramasB >= newAB[i])
                {
                    ramasB -= newAB[i];
                    myaux -= 1;
                }
            }
            rez = min(rez, myaux);
        }

        /*int pozAB = 0, pozBB = 0;
        while((pozAB < newAB.size() || pozBB < v[B][B].size()) && ramasB > 0)
        {
            if(pozBB == v[B][B].size() || newAB[pozAB] < v[B][B][pozBB])
            {
                assert(pozAB < newAB.size());
                if(ramasB >= newAB[pozAB])
                {
                    aux -= 2;
                    pozAB++;
                }
                else
                    break;
            }
            else
            {
                if(ramasB >= v[B][B][pozBB])
                {
                    aux -= 2;
                    pozBB++;
                }
                else
                    break;
            }
        }
        rez = min(rez, aux);
        */
    }

    return rez;
}
int solve_two_dominants(vector<int> cnt, int d1, int d2)
{

}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    string s;
    cin>>s;
    assert(s.size() == n);
    for(int i=0;i<n;i++)
    {
        if(s[i] != '?' && i!=n-1)
        {
            int poz = i + 1;
            while(poz < n && s[poz] == '?')
                poz++;
            v[s[i]-'A'][s[poz]-'A'].push_back(poz - i - 1);
            v[s[poz]-'A'][s[i]-'A'].push_back(poz - i - 1);
            //cerr<<s[i]<<" "<<s[poz]<<": "<<poz-i-1<<" v\n";
        }
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            sort(v[i][j].begin(), v[i][j].end());
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        vector<int> cnt(3);
        for(int c=0;c<3;c++)
            cin>>cnt[c];
        //cerr<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<" zzz\n";

        vector<int> dominants, maybes;
        for(int d=0;d<3;d++)
        {
            int sum = 0;
            for(int u=0;u<3;u++)
            {
                for(int x:v[d][u])
                    sum += x;
            }
            if(cnt[d] > sum)
            {
                dominants.push_back(d);
            }
            else if(sum == cnt[d])
            {
                maybes.push_back(d);
            }
        }
        assert(dominants.size() <= 2);

        if(dominants.empty())
        {
            cout<<solve_dominant(cnt, 0)<<"\n";
        }
        else if(dominants.size() == 1)
        {
            cout<<solve_dominant(cnt, dominants[0])<<"\n";
        }
        else
        {
            assert(dominants.size() == 2);
            assert(0);
            cout<<solve_two_dominants(cnt, dominants[0], dominants[1])<<"\n";
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int solve_two_dominants(std::vector<int>, int, int)':
Main.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
  115 | }
      | ^

• Subtask 1: 0 / 0
• Subtask 2: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 13
• Subtask 5: 0 / 18
• Subtask 6: 0 / 12
• Subtask 7: 0 / 8
• Subtask 8: 0 / 13
• Subtask 9: 0 / 25