oj.uz

답안 #587067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587067 2022-07-01T09:34:24 Z maomao90 게임 (APIO22_game) C++17
2 / 100
 10 ms 14364 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
 
#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)
 
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
 
typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef tuple<int, int, int> iii;
 
#ifndef DEBUG
#define cerr if (0) cerr
#endif
 
const int MAXN = 300005;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
 
int n, k;
vi adj[MAXN], radj[MAXN];
int lft[MAXN], rht[MAXN];
bool ans;
 
void init(int N, int K) {
    n = N; k = K;
    REP (i, 0, k) {
        lft[i] = rht[i] = i;
    }
    REP (i, k, n) {
        lft[i] = -1; rht[i] = k;
    }
}

void propo(int u);

void fix(int u, int v) {
    if (rht[u] < lft[v]) {
        return;
    }
    if (rht[v] < lft[u]) {
        ans = 1;
        return;
    }
    if (lft[u] == lft[v] && rht[u] == rht[v]) {
        return;
    }
    if (lft[u] <= lft[v] && rht[v] <= rht[u]) {
        rht[u] = lft[u] + rht[u] >> 1;
        if (lft[u] == rht[u]) {
            ans = 1;
            return;
        }
        propo(u);
    } else if (lft[v] <= lft[u] && rht[u] <= rht[v]) {
        lft[v] = (lft[v] + rht[v] >> 1) + 1;
        if (lft[u] == rht[u]) {
            ans = 1;
            return;
        }
        propo(v);
    }
}

void propo(int u) {
    for (int v : radj[u]) {
        fix(v, u);
    }
    for (int v : adj[u]) {
        fix(u, v);
    }
}
 
int add_teleporter(int u, int v) {
    if (u < k && v < k) {
        if (v <= u) {
            return 1;
        } else {
            return 0;
        }
    }
    adj[u].pb(v);
    radj[v].pb(u);
    fix(u, v);
    return ans;
}

Compilation message

game.cpp: In function 'void fix(int, int)':
game.cpp:63:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         rht[u] = lft[u] + rht[u] >> 1;
      |                  ~~~~~~~^~~~~~~~
game.cpp:70:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         lft[v] = (lft[v] + rht[v] >> 1) + 1;
      |                   ~~~~~~~^~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14320 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 10 ms 14312 KB Output is correct
4 Correct 9 ms 14364 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 7 ms 14288 KB Output is correct
7 Correct 7 ms 14288 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14320 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 10 ms 14312 KB Output is correct
4 Correct 9 ms 14364 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 7 ms 14288 KB Output is correct
7 Correct 7 ms 14288 KB Output is correct
8 Incorrect 7 ms 14288 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14320 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 10 ms 14312 KB Output is correct
4 Correct 9 ms 14364 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 7 ms 14288 KB Output is correct
7 Correct 7 ms 14288 KB Output is correct
8 Incorrect 7 ms 14288 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14320 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 10 ms 14312 KB Output is correct
4 Correct 9 ms 14364 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 7 ms 14288 KB Output is correct
7 Correct 7 ms 14288 KB Output is correct
8 Incorrect 7 ms 14288 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14320 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 10 ms 14312 KB Output is correct
4 Correct 9 ms 14364 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 7 ms 14288 KB Output is correct
7 Correct 7 ms 14288 KB Output is correct
8 Incorrect 7 ms 14288 KB Wrong Answer[1]
9 Halted 0 ms 0 KB -