oj.uz

답안 #962761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
962761 2024-04-14T07:59:25 Z GrindMachine 길고양이 (JOI20_stray) C++17
76 / 100
 36 ms 19572 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

/*

refs:
edi
https://codeforces.com/blog/entry/74871?#comment-591498

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

#include "Anthony.h"

namespace anthony {
    set<string> st1,st2;
    string chain = "";

    void precalc(){
        int n = 6;
        rep(mask,1<<n){
            string s(2*n,'?');
            rep(i,n){
                ll b = 0;
                if(mask&(1<<i)){
                    b = 1;
                }
                s[i] = s[i+n] = char('0'+b);
            }

            st1.clear(), st2.clear();
            rep(i,n){
                string t = string(s.begin()+i,s.begin()+i+n);
                st1.insert(t);
                reverse(all(t));
                st2.insert(t);
            }

            bool ok = true;
            trav(t,st1){
                if(st2.count(t)){
                    ok = false;
                }
            }

            if(ok){
                chain = string(s.begin(),s.begin()+n);
                return;
            }
        }
    }

    vector<pii> adj[N];
    vector<int> val;

    void dfs1(int u, int p, int prev_typ, int ptr){
        for(auto [v,id] : adj[u]){
            if(v == p) conts;
            if(sz(adj[v]) == 2){
                int nxt_ptr = 0;
                if(ptr != -1){
                    nxt_ptr = (ptr+1)%6;
                }
                else{
                    if(prev_typ == 0){
                        nxt_ptr = 0;
                    }
                    else{
                        nxt_ptr = 2;
                    }
                }

                val[id] = chain[nxt_ptr]-'0';
                dfs1(v,u,-1,nxt_ptr);
            }
            else{
                int nxt_typ = 0;
                if(prev_typ != -1){
                    nxt_typ = prev_typ^1;
                }
                else{
                    nxt_typ = (chain[ptr]-'0')^1;
                }

                val[id] = nxt_typ;
                dfs1(v,u,nxt_typ,-1);
            }
        }
    }

}  // namespace

using namespace anthony;

std::vector<int> Mark(int n, int m, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    // std::vector<int> X(M);
    // for (int i = 0; i < M; ++i) {
    //     X[i] = FunctionExample(i, A);
    // }
    // return X;

    precalc();
    rep(i,m){
        int u = U[i], v = V[i];
        adj[u].pb({v,i}), adj[v].pb({u,i});
    }

    val = vector<int>(m,-1);
    dfs1(0,-1,1,-1);

    debug(val);
    return val;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

// #ifdef LOCAL
// #include "debug.h"
// #else
// #define debug(x) 42
// #endif

/*

refs:
edi
https://codeforces.com/blog/entry/74871?#comment-591498

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Catherine.h"

namespace catherine {
    int A,B;
    set<string> st1,st2;
    string chain = "";

    void precalc(){
        int n = 6;
        rep(mask,1<<n){
            string s(2*n,'?');
            rep(i,n){
                ll b = 0;
                if(mask&(1<<i)){
                    b = 1;
                }
                s[i] = s[i+n] = char('0'+b);
            }

            st1.clear(), st2.clear();
            rep(i,n){
                string t = string(s.begin()+i,s.begin()+i+n);
                st1.insert(t);
                reverse(all(t));
                st2.insert(t);
            }

            bool ok = true;
            trav(t,st1){
                if(st2.count(t)){
                    ok = false;
                }
            }

            if(ok){
                chain = string(s.begin(),s.begin()+n);
                return;
            }
        }
    }

    int move_num = 0;
    bool decided = false;
    int prev_edge = 0;
    string curr_chain = "";

}  // namespace

using namespace catherine;

void Init(int A_, int B_) {
    A = A_;
    B = B_;
    precalc();
}

int Move(std::vector<int> y) {
    // ++variable_example;
    // for (int j = 0; j < A; ++j) {
    //     if (y[j] != 0) {
    //       return j;
    //     }
    // }
    // return -1;

    int sum = y[0]+y[1];
    if(!sum){
        decided = true;
        return -1;
    }

    if(decided){
        if(sum == 1){
            if(y[0]) prev_edge = 0;
            else prev_edge = 1;
        }
        else{
            prev_edge ^= 1;
        }

        return prev_edge;
    }

    move_num++;
    if(move_num == 1){
        if(sum == 1){
            if(y[0]) prev_edge = 0;
            else prev_edge = 1;
            decided = true;
            return prev_edge;
        }
        else if(sum >= 3){
            if(y[0] == 1) prev_edge = 0;
            else prev_edge = 1;
            decided = true;
            return prev_edge;
        }
        else{
            if(y[0]) prev_edge = 0;
            else prev_edge = 1;
            curr_chain.pb(char('0'+prev_edge));
            return prev_edge;
        }
    }

    if(sum >= 2){
        decided = true;
        y[prev_edge]++;
        int nxt_edge = 0;
        if(y[0] == 1) nxt_edge = 0;
        else nxt_edge = 1;

        if(nxt_edge == prev_edge) return -1;
        else return prev_edge = nxt_edge;
    }

    if(y[0]) prev_edge = 0;
    else prev_edge = 1;

    if(move_num == 7){
        decided = true;
        if(st1.count(curr_chain)){
            // wrong direction
            prev_edge = curr_chain.back()-'0';
            return -1;
        }
        else{
            return prev_edge;
        }
    }

    curr_chain.pb(char('0'+prev_edge));
    return prev_edge;
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:18: warning: statement has no effect [-Wunused-value]
   59 | #define debug(x) 42
      |                  ^~
Anthony.cpp:161:5: note: in expansion of macro 'debug'
  161 |     debug(val);
      |     ^~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18036 KB Output is correct
2 Correct 1 ms 3088 KB Output is correct
3 Correct 25 ms 16752 KB Output is correct
4 Correct 33 ms 19572 KB Output is correct
5 Incorrect 31 ms 19564 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 18036 KB Output is correct
2 Correct 1 ms 3088 KB Output is correct
3 Correct 25 ms 16752 KB Output is correct
4 Correct 33 ms 19572 KB Output is correct
5 Incorrect 31 ms 19564 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 15820 KB Output is correct
2 Correct 1 ms 3092 KB Output is correct
3 Correct 23 ms 14452 KB Output is correct
4 Correct 33 ms 17424 KB Output is correct
5 Incorrect 31 ms 17456 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 15820 KB Output is correct
2 Correct 1 ms 3092 KB Output is correct
3 Correct 23 ms 14452 KB Output is correct
4 Correct 33 ms 17424 KB Output is correct
5 Incorrect 31 ms 17456 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3344 KB Output is correct
2 Correct 1 ms 3100 KB Output is correct
3 Correct 1 ms 3352 KB Output is correct
4 Correct 2 ms 3352 KB Output is correct
5 Correct 2 ms 3360 KB Output is correct
6 Correct 2 ms 3352 KB Output is correct
7 Correct 2 ms 3352 KB Output is correct
8 Correct 2 ms 3360 KB Output is correct
9 Correct 2 ms 3356 KB Output is correct
10 Correct 2 ms 3356 KB Output is correct
11 Correct 3 ms 3356 KB Output is correct
12 Correct 2 ms 3344 KB Output is correct
13 Correct 2 ms 3356 KB Output is correct
14 Correct 2 ms 3352 KB Output is correct
15 Correct 2 ms 3360 KB Output is correct
16 Correct 1 ms 3352 KB Output is correct
17 Correct 2 ms 3352 KB Output is correct
18 Correct 2 ms 3344 KB Output is correct
19 Correct 3 ms 3352 KB Output is correct
20 Correct 2 ms 3344 KB Output is correct
21 Correct 2 ms 3348 KB Output is correct
22 Correct 2 ms 3344 KB Output is correct
23 Correct 2 ms 3344 KB Output is correct
24 Correct 2 ms 3344 KB Output is correct
25 Correct 1 ms 3348 KB Output is correct
26 Correct 3 ms 3352 KB Output is correct
27 Correct 2 ms 3352 KB Output is correct
28 Correct 1 ms 3352 KB Output is correct

Subtask #6
71.0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 13240 KB Output is correct
2 Correct 28 ms 14404 KB Output is correct
3 Correct 2 ms 3100 KB Output is correct
4 Correct 26 ms 12860 KB Output is correct
5 Correct 31 ms 16076 KB Output is correct
6 Correct 30 ms 15924 KB Output is correct
7 Correct 26 ms 14976 KB Output is correct
8 Correct 26 ms 15612 KB Output is correct
9 Correct 31 ms 16472 KB Output is correct
10 Correct 31 ms 16472 KB Output is correct
11 Correct 30 ms 16468 KB Output is correct
12 Correct 31 ms 16492 KB Output is correct
13 Correct 32 ms 16384 KB Output is correct
14 Correct 30 ms 16448 KB Output is correct
15 Correct 33 ms 16360 KB Output is correct
16 Correct 31 ms 16352 KB Output is correct
17 Correct 28 ms 16168 KB Output is correct
18 Correct 28 ms 16180 KB Output is correct
19 Correct 28 ms 16036 KB Output is correct
20 Correct 32 ms 16200 KB Output is correct
21 Correct 31 ms 16112 KB Output is correct
22 Correct 28 ms 16212 KB Output is correct
23 Correct 25 ms 13664 KB Output is correct
24 Correct 26 ms 13800 KB Output is correct
25 Correct 26 ms 14080 KB Output is correct
26 Correct 25 ms 14156 KB Output is correct
27 Correct 30 ms 14912 KB Output is correct
28 Correct 28 ms 14948 KB Output is correct
29 Correct 27 ms 15196 KB Output is correct
30 Correct 27 ms 15184 KB Output is correct
31 Correct 24 ms 13560 KB Output is correct
32 Correct 24 ms 13612 KB Output is correct
33 Correct 25 ms 14160 KB Output is correct
34 Correct 25 ms 14136 KB Output is correct
35 Correct 27 ms 14924 KB Output is correct
36 Correct 27 ms 15144 KB Output is correct
37 Correct 33 ms 14912 KB Output is correct
38 Correct 27 ms 15112 KB Output is correct
39 Correct 28 ms 14940 KB Output is correct
40 Correct 27 ms 14936 KB Output is correct
41 Correct 30 ms 15512 KB Output is correct
42 Correct 28 ms 15352 KB Output is correct
43 Correct 28 ms 15440 KB Output is correct
44 Correct 30 ms 15420 KB Output is correct
45 Correct 28 ms 15444 KB Output is correct
46 Correct 36 ms 15376 KB Output is correct
47 Correct 28 ms 14632 KB Output is correct
48 Correct 30 ms 14840 KB Output is correct
49 Correct 27 ms 14420 KB Output is correct
50 Correct 27 ms 14668 KB Output is correct
51 Correct 24 ms 14168 KB Output is correct
52 Correct 26 ms 14164 KB Output is correct
53 Correct 25 ms 13972 KB Output is correct
54 Correct 26 ms 14032 KB Output is correct
55 Correct 27 ms 13912 KB Output is correct
56 Correct 25 ms 13960 KB Output is correct
57 Correct 26 ms 14104 KB Output is correct
58 Correct 25 ms 14164 KB Output is correct
59 Correct 25 ms 13904 KB Output is correct
60 Correct 25 ms 13904 KB Output is correct

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 13172 KB Output is correct
2 Correct 27 ms 14772 KB Output is correct
3 Correct 1 ms 3084 KB Output is correct
4 Correct 20 ms 13016 KB Output is correct
5 Correct 31 ms 15816 KB Output is correct
6 Correct 31 ms 15988 KB Output is correct
7 Correct 28 ms 14968 KB Output is correct
8 Incorrect 25 ms 15028 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -