Submission #866718

#	Time	Username	Problem	Language	Result	Execution time	Memory
866718		vjudge1	Monster Game (JOI21_monster)	C++17	0 / 100	133 ms	928 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"
using namespace std;

/*vector<int> a;

bool Query(int x, int y)
{
    //cout << "? " << x << " " << y << '\n';
    bool win=false;
    if (a[x]-a[y]>1 || a[y]-a[x]==1)
        win=true;
    //cout << win << '\n';

    return win;
}*/

bool compare(int x, int y)
{
    return !Query(x, y);
}

int firstelement(int x, int n)
{
    int win=0;
    for (int i=0; i<n; i++)
    {
        if (i==x)
            continue;
        win=win+Query(x, i);
    }
    if (win<2)
        return 0;

    return 1;
}

vector<int> Solve(int n)
{
    int order[n];
    for (int i=0; i<n; i++)
        order[i]=i;
    sort(order, order+n, compare);
    vector<int> win;
    for (int i=1; i<n; i++)
        if (Query(order[0], order[i]))
            win.push_back(i);
    int current;
    if (win.size()<2)
        current=firstelement(order[win[0]], n);
    else
        current=win[win.size()-2];
    vector<int> strength;
    int last=-1, check=0, x=current;
    while (x>last)
    {
        strength.push_back(x);
        x=x-1;
    }
    while (strength.size()<n)
    {
        for (int i=strength.size(); i<n; i++)
            if (Query(order[check], order[i]))
            {
                check=strength.size();
                last=current;
                current=current+(i-strength.size()+1);
                break;
            }
        x=current;
        while (x>last)
        {
            strength.push_back(x);
            x=x-1;
        }
    }
    vector<int> finalstrength(n);
    for (int i=0; i<n; i++)
        finalstrength[order[i]]=strength[i];

    return finalstrength;
}

/*int main()
{
    a={3, 1, 4, 2, 0};
    for (auto x : a)
        cout << x << " ";
    cout << '\n';
    vector<int> t=Solve(5);
    for (auto x : t)
        cout << x << " ";

    return 0;
}*/



/*#include <bits/stdc++.h>
#include "monster.h"
using namespace std;

vector<int> a;

bool Query(int x, int y)
{
    cout << "? " << x << " " << y << '\n';
    bool win=false;
    if (a[x]-a[y]>1 || a[y]-a[x]==1)
        win=true;
    cout << win << '\n';

    return win;
}

vector<int> Solve(int n)
{
    int wins[n]={0};
    bool outcome[n][n];
    vector<int> strength(n);
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
        {
            outcome[i][j]=Query(i, j);
            if (outcome[i][j]==true)
                wins[i]=wins[i]+1;
            else
                wins[j]=wins[j]+1;
        }
    cout << "wins\n";
    for (int i=0; i<n; i++)
        cout << wins[i] << " ";
    cout << '\n';
    for (int i=0; i<n; i++)
        strength[i]=wins[i];
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
        {
            if (wins[i]==n-2 && wins[j]==n-2)
            {
                strength[i]=n-1;
                strength[j]=n-2;
                if (outcome[i][j]==true)
                    swap(strength[i], strength[j]);

            }
            if (wins[i]==1 && wins[j]==1)
            {
                strength[i]=1;
                strength[j]=0;
                if (outcome[i][j]==true)
                    swap(strength[i], strength[j]);

            }
        }

    return strength;
}

int main()
{
    a={3, 1, 4, 2, 0};
    vector<int> t=Solve(5);
    for (auto x : t)
        cout << x << " ";

    return 0;
}*/

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     while (strength.size()<n)
      |            ~~~~~~~~~~~~~~~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75