oj.uz

답안 #1050905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050905 2024-08-09T16:41:02 Z Andrey Monster Game (JOI21_monster) C++17
0 / 100
 51 ms 424 KB 
#include "monster.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> haha(0);

void dude(int l, int r) {
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    dude(l,mid);
    dude(mid+1,r);
    vector<int> wow(0);
    int x = l,y = mid+1;
    for(int i = 0; i < r-l+1; i++) {
        if(x != mid+1 && (y == r+1 || Query(haha[y],haha[x]))) {
            wow.push_back(haha[x]);
            x++;
        }
        else {
            wow.push_back(haha[y]);
            y++;
        }
    }
    for(int i = 0; i < wow.size(); i++) {
        haha[i+l] = wow[i];
    }
}

vector<int> Solve(int n) {
    for(int i = 0; i < n; i++) {
        haha.push_back(i);
    }
    dude(0,n-1);
    vector<int> ans(n);
    bool yeah = true;
    vector<bool> bruh(n);
    int big;
    for(int i = 2; i < n; i++) {
        if(Query(haha[0],haha[i])) {
            bruh[i] = true;
            if(!yeah) {
                big = i;
                break;
            }
        }
        else {
            if(yeah && ((i == 3) || (i >= 3 && Query(haha[i-1],haha[1])))) {
                big = i-1;
                yeah = false;
                break;
            }
            yeah = false;
        }
    }
    if(yeah) {
        if(Query(haha[n-1],haha[1])) {
            for(int i = 0; i < n-1; i++) {
                ans[haha[i]] = n-2-i;
            }
            ans[haha[n-1]] = n-1;
        }
        else {
            for(int i = 0; i < n; i++) {
                ans[haha[i]] = n-1-i;
            }
        }
        return ans;
    }
 /*   for(int i = 0; i < n; i++) {
        cout << haha[i] << " ";
    }
    cout << endl;*/
    int p = big-1;
    bool no = true;
    if(big == 2) {
        no = false;
        if(Query(haha[0],haha[3])) {
            ans[haha[0]] = 2;
            ans[haha[1]] = 1;
            ans[haha[2]] = 0;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else if(Query(haha[1],haha[3])) {
            ans[haha[0]] = 0;
            ans[haha[1]] = 2;
            ans[haha[2]] = 1;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else if(Query(haha[2],haha[3])) {
            ans[haha[0]] = 1;
            ans[haha[1]] = 0;
            ans[haha[2]] = 2;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else {
            int q;
            for(int i = 5; i <= n; i++) {
                if(i == n || (!Query(haha[3],haha[i]))) {
                    if(Query(haha[0],haha[i-1]) || Query(haha[1],haha[i-1]) || Query(haha[2],haha[i-1])) {
                        q = i-1;
                    }
                    else {
                        q = i-2;
                    }
                }
            }
            if(Query(haha[0],haha[q])) {
                ans[haha[0]] = 2;
                ans[haha[1]] = 1;
                ans[haha[2]] = 0;
            }
            else if(Query(haha[1],haha[q])) {
                ans[haha[0]] = 0;
                ans[haha[1]] = 2;
                ans[haha[2]] = 1;
            }
            else {
                ans[haha[0]] = 1;
                ans[haha[1]] = 0;
                ans[haha[2]] = 2;
            }
            for(int i = 3; i <= q; i++) {
                ans[haha[i]] = q-(i-3);
            }
            big = q;
            p = 2;
        }
    }
    else {
        while(p > 1 && !bruh[p]) {
            p--;
        }
        if(p == 1 && Query(haha[1],haha[big])) {
            p--;
        }
    }
   /* for(int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;*/
    if(no) {
        for(int i = 0; i <= p; i++) {
            ans[haha[i]] = p-i;
        }
        for(int i = p+1; i <= big; i++) {
            ans[haha[i]] = big-(i-p-1);
        }
    }
    int y = p+1,x = big+1;
    for(int i = big+1; i < n; i++) {
        if(Query(haha[y],haha[i])) {
            for(int j = x; j <= i; j++) {
                ans[haha[j]] = i-(j-x);
            }
            y = x;
            x = i+1;
        }
    }

    return ans;
}

Compilation message

monster.cpp: In function 'void dude(int, int)':
monster.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < wow.size(); i++) {
      |                    ~~^~~~~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:75:9: warning: 'big' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     int p = big-1;
      |         ^
monster.cpp:157:17: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |     int y = p+1,x = big+1;
      |                 ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 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 Incorrect 0 ms 344 KB Wrong Answer [3]
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 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 Incorrect 0 ms 344 KB Wrong Answer [3]
11 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 424 KB Output is correct
2 Incorrect 51 ms 344 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -