oj.uz

Submission #866718

# Submission time Handle Problem Language Result Execution time Memory
866718 2023-10-26T21:16:03 Z vjudge1 Monster Game (JOI21_monster) C++17
0 / 100
 133 ms 928 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 9 ms 440 KB Output is correct
17 Correct 9 ms 436 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 9 ms 436 KB Output is correct
21 Incorrect 1 ms 344 KB Wrong Answer [3]
22 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 9 ms 440 KB Output is correct
17 Correct 9 ms 436 KB Output is correct
18 Correct 9 ms 600 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 9 ms 436 KB Output is correct
21 Incorrect 1 ms 344 KB Wrong Answer [3]
22 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 60 ms 928 KB Partially correct
2 Partially correct 63 ms 672 KB Partially correct
3 Partially correct 70 ms 668 KB Partially correct
4 Partially correct 58 ms 596 KB Partially correct
5 Partially correct 64 ms 436 KB Partially correct
6 Partially correct 54 ms 424 KB Partially correct
7 Partially correct 60 ms 416 KB Partially correct
8 Partially correct 48 ms 412 KB Partially correct
9 Partially correct 50 ms 596 KB Partially correct
10 Partially correct 72 ms 420 KB Partially correct
11 Partially correct 58 ms 672 KB Partially correct
12 Partially correct 79 ms 668 KB Partially correct
13 Incorrect 133 ms 416 KB Wrong Answer [6]
14 Halted 0 ms 0 KB -