oj.uz

답안 #423532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423532 2021-06-11T08:57:38 Z 최서현(#7497) Monster Game (JOI21_monster) C++17
0 / 100
 69 ms 928 KB 
#include "monster.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <tuple>
#include <map>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;

using namespace std;

namespace {
    vector<int> ret;
    map<pii, int> M;
    bool Q(int x, int y)
    {
        if(M.count({x, y})) return M[{x, y}];
        if(M.count({y, x})) return !M[{y, x}];
        return M[{x, y}] = Query(x, y);
    }
    void f(int s, int e)
    {
        if(s + 1 == e) return;
        int mid = s + e >> 1;
        f(s, mid);
        f(mid, e);
        int pt = 0, pt1 = s, pt2 = mid;
        int tmp[e - s];
        while(pt1 < mid && pt2 < e)
        {
            if(Q(ret[pt1], ret[pt2])) tmp[pt++] = ret[pt2++];
            else tmp[pt++] = ret[pt1++];
        }
        while(pt1 < mid) tmp[pt++] = ret[pt1++];
        while(pt2 < e) tmp[pt++] = ret[pt2++];
        for(int i = s; i < e; ++i) ret[i] = tmp[i - s];
    }
}

vector<int> Solve(int N)
{
    ret.resize(N);
    for(int i = 0; i < N; ++i) ret[i] = i;

    f(0, N);

    int cnt = 0, pr = 0;;
    for(int i = 1; i < N; ++i) if(Q(ret[0], ret[i])) ++cnt;
    if(cnt == 1)
    {
        int cnt2 = 0;
        for(int i = 2; i < N; ++i) if(Q(ret[1], ret[i])) ++cnt2;
        if(cnt2 == 0)
        {
            swap(ret[0], ret[1]);
            pr = 1;
        }
        else
        {
            pr = 0;
        }
    }
    else
    {
        reverse(ret.begin(), ret.begin() + cnt + 1);
        pr = cnt;
    }
    for(int i = pr + 1; i < N; ++i)
    {
        if(Q(ret[pr], ret[i]))
        {
            reverse(ret.begin() + pr + 1, ret.begin() + i + 1);
            pr = i;
        }
    }

    vector<int> rret(N);
    for(int i = 0; i < N; ++i) rret[ret[i]] = i;

    for(auto i : ret) cout << i << ' '; cout << endl;
    return rret;
}

Compilation message

monster.cpp: In function 'bool {anonymous}::Q(int, int)':
monster.cpp:30:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   30 |         return M[{x, y}] = Query(x, y);
monster.cpp: In function 'void {anonymous}::f(int, int)':
monster.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = s + e >> 1;
      |                   ~~^~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:91:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   91 |     for(auto i : ret) cout << i << ' '; cout << endl;
      |     ^~~
monster.cpp:91:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |     for(auto i : ret) cout << i << ' '; cout << endl;
      |                                         ^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 200 KB Wrong Answer [0]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 200 KB Wrong Answer [0]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 928 KB Wrong Answer [0]
2 Halted 0 ms 0 KB -