oj.uz

Submission #726925

# Submission time Handle Problem Language Result Execution time Memory
726925 2023-04-19T15:08:21 Z Vu_CG_Coder Game (APIO22_game) C++17
2 / 100
 9 ms 14416 KB 
/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du    */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include "game.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
    if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
    if (res > val) { res = val; return true; } return false; }
 
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int Nx = 3e5 + 100;
 
int val[2][Nx];
vector <int> a[2][Nx];
int n , k;
int ok;
 
void init(int _n , int _k)
{
    n = _n;
    k = _k;
 
    for (int i = 1 ; i <= k ; i++) 
    {
        val[0][i] = i;
        val[1][i] = i - 1;
    }
 
    for (int i = k + 1 ; i <= n ; i++)
    {
        val[0][i] = n + 1;
        val[1][i] = 0;
    }
}
 
void dfs(int id , int u, int gt)
{
    int old = val[id][u];
    if (id) maximize(val[id][u],gt);
    else minimize(val[id][u],gt);
 
    if (val[1][u] >= val[0][u]) {
        ok = 1;
        return ;
    }
 
    if (old == val[id][u]) return ;
 
    int x = old^val[id^1][u];
    int y = val[id][u]^val[id^1][u];
 
    for (int i = 20 ; i >= 0 ; i--) if (x&(1<<i)) 
    {
        x = i;
        break;
    }
 
    for (int i = 20 ; i >= 0 ; i--) if (y&(1<<i)) 
    {
        y = i;
        break;
    }
 
    if (x < y)
    {
        for (int tt = 0 ; tt < 2 ; tt++)
            for (int v : a[tt][u])
                dfs(tt,v,val[tt][u]);
    }
}
 
int add_teleporter(int u, int v)
{
    u++;
    v++;
    if (u > v && u <= k) return 1;
 
    a[1][u].push_back(v);
    a[0][v].push_back(u);
 
    ok = 0;
 
    int gt = val[1][u];
    if (u <= k) gt = u;
    dfs(1,v,gt);
 
    gt = val[0][v];
    if (v <= k) gt = v;
    dfs(0,u,gt);
 
    if (ok == 1) return 1;
    return 0;
}
 
 
// int main()
// {
//     if(fopen(TASK".inp", "r")){
//     freopen(TASK".inp","r",stdin);
//     freopen(TASK".out","w",stdout);
//     }
 
//     int x , y , z;
//     cin >> x >> y >> z;
 
//     init(x,y);
 
//     for (int i = 1 ; i <= z ; i++)
//     {
//         int a , b;
//         cin >> a >> b;
//         if (add_teleporter(a,b)) 
//         {
//             (cout << i);
//             return 0;
//         }
//     } 
//     return 0;
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14340 KB Output is correct
5 Correct 8 ms 14288 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14288 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14340 KB Output is correct
5 Correct 8 ms 14288 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 8 ms 14336 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Incorrect 8 ms 14288 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14340 KB Output is correct
5 Correct 8 ms 14288 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 8 ms 14336 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Incorrect 8 ms 14288 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14340 KB Output is correct
5 Correct 8 ms 14288 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 8 ms 14336 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Incorrect 8 ms 14288 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14288 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 9 ms 14340 KB Output is correct
5 Correct 8 ms 14288 KB Output is correct
6 Correct 8 ms 14416 KB Output is correct
7 Correct 8 ms 14288 KB Output is correct
8 Correct 8 ms 14288 KB Output is correct
9 Correct 8 ms 14336 KB Output is correct
10 Correct 7 ms 14288 KB Output is correct
11 Incorrect 8 ms 14288 KB Wrong Answer[1]
12 Halted 0 ms 0 KB -