제출 #1166573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166573		Pacybwoah	Broken Device (JOI17_broken_device)	C++20	100 / 100	25 ms	1608 KiB

Anna

#include "Annalib.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
namespace{
    vector<vector<int>> vec = {{118, 114}, {116, 28}, {145, 46}, {8, 82}, {26, 37}, {141, 0}, {16, 85}, {147, 73}, {6, 109}, {63, 56}, {64, 121}, {98, 23}, {70, 80}, {22, 19}, {50, 60}, {27, 7}, {71, 146}, {17, 99}, {97, 107}, {76, 90}, {32, 18}, {105, 92}, {12, 69}, {132, 30}, {40, 15}, {131, 62}, {87, 142}, {136, 9}, {44, 33}, {41, 2}, {36, 45}, {148, 1}, {139, 5}, {106, 20}, {21, 83}, {93, 68}, {138, 101}, {11, 79}, {104, 86}, {13, 14}, {67, 42}, {124, 125}, {130, 65}, {112, 89}, {95, 100}, {75, 102}, {126, 4}, {31, 88}, {129, 96}, {52, 120}, {25, 110}, {119, 149}, {74, 111}, {81, 48}, {51, 135}, {38, 113}, {35, 10}, {134, 77}, {61, 78}, {57, 72}, {123, 94}, {43, 137}, {34, 53}, {66, 29}, {54, 3}, {39, 128}, {143, 103}, {59, 108}, {84, 47}, {58, 144}, {122, 115}, {49, 117}, {127, 140}, {91, 24}, {133, 55}};
    const __int128_t mod = 1412585929026715559;
    __int128_t power(__int128_t a, __int128_t b){
        if(b == 0) return 1;
        if(b & 1) return power(a, b - 1) * a % mod;
        __int128_t tmp = power(a, b / 2);
        return tmp * tmp % mod;
    }
    __int128_t inv(__int128_t a){
        return power(a, mod - 2);
    }
    ll hashs(ll x){
        __int128_t tmp = x;
        tmp = ((tmp * 7 % mod * inv(4) % mod) + 242342342) % mod * inv(39) % mod;
        return ll(tmp);
    }
}
void Anna(int n, ll x, int k, int p[]){
    vector<int> ok(n, 1);
    for(int i = 0; i < k; i++) ok[p[i]] = 0;
    x = hashs(x);
    vector<int> tri;
    while(x > 0){
        tri.push_back(x % 3);
        x /= 3;
    }
    int now = 0, sz = (int)tri.size();
    for(int i = 0; i < n / 2; i++){
        if(ok[vec[i][0]] && ok[vec[i][1]]){
            if(now >= sz){
                Set(vec[i][0], 0);
                Set(vec[i][1], 0);
            }
            else{
                // 01 10 11
                if(tri[now] == 0){
                    Set(vec[i][0], 0);
                    Set(vec[i][1], 1);
                }
                else if(tri[now] == 1){
                    Set(vec[i][0], 1);
                    Set(vec[i][1], 0);
                }
                else{
                    Set(vec[i][0], 1);
                    Set(vec[i][1], 1);
                }
                now++;
            }
        }
        else if(ok[vec[i][0]]){
            // 10
            if(now >= sz){
                Set(vec[i][0], 0);
                Set(vec[i][1], 0);
            }
            else if(tri[now] == 1){
                Set(vec[i][0], 1);
                Set(vec[i][1], 0);
                now++;
            }
            else{
                Set(vec[i][0], 0);
                Set(vec[i][1], 0);
            }
        }
        else if(ok[vec[i][1]]){
            // 01
            if(now >= sz){
                Set(vec[i][0], 0);
                Set(vec[i][1], 1);
            }
            else if(tri[now] == 0){
                Set(vec[i][0], 0);
                Set(vec[i][1], 1);
                now++;
            }
            else{
                Set(vec[i][0], 0);
                Set(vec[i][1], 0);
            }
        }
        else{
            Set(vec[i][0], 0);
            Set(vec[i][1], 0);
        }
    }
}

Bruno

#include "Brunolib.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
namespace{
    vector<vector<int>> vec = {{118, 114}, {116, 28}, {145, 46}, {8, 82}, {26, 37}, {141, 0}, {16, 85}, {147, 73}, {6, 109}, {63, 56}, {64, 121}, {98, 23}, {70, 80}, {22, 19}, {50, 60}, {27, 7}, {71, 146}, {17, 99}, {97, 107}, {76, 90}, {32, 18}, {105, 92}, {12, 69}, {132, 30}, {40, 15}, {131, 62}, {87, 142}, {136, 9}, {44, 33}, {41, 2}, {36, 45}, {148, 1}, {139, 5}, {106, 20}, {21, 83}, {93, 68}, {138, 101}, {11, 79}, {104, 86}, {13, 14}, {67, 42}, {124, 125}, {130, 65}, {112, 89}, {95, 100}, {75, 102}, {126, 4}, {31, 88}, {129, 96}, {52, 120}, {25, 110}, {119, 149}, {74, 111}, {81, 48}, {51, 135}, {38, 113}, {35, 10}, {134, 77}, {61, 78}, {57, 72}, {123, 94}, {43, 137}, {34, 53}, {66, 29}, {54, 3}, {39, 128}, {143, 103}, {59, 108}, {84, 47}, {58, 144}, {122, 115}, {49, 117}, {127, 140}, {91, 24}, {133, 55}};
    const __int128_t mod = 1412585929026715559;
    __int128_t power(__int128_t a, __int128_t b){
        if(b == 0) return 1;
        if(b & 1) return power(a, b - 1) * a % mod;
        __int128_t tmp = power(a, b / 2);
        return tmp * tmp % mod;
    }
    __int128_t inv(__int128_t a){
        return power(a, mod - 2);
    }
    ll hashs(ll x){
        __int128_t tmp = x;
        tmp = ((tmp * 7 % mod * inv(4) % mod) + 242342342) % mod * inv(39) % mod;
        return ll(tmp);
    }
    ll unhash(ll x){
        __int128_t tmp = x;
        tmp = (tmp * 39 % mod - 242342342 + mod) % mod * 4 % mod * inv(7) % mod;
        return ll(tmp);
    }
}
long long Bruno(int n, int a[]){
    ll ans = 0, now = 1;
    for(int i = 0; i < n / 2; i++){
        if(a[vec[i][0]] == 0 && a[vec[i][1]] == 0) continue;
        else{
            // 01 10 11
            if(a[vec[i][0]] == 1 && a[vec[i][1]] == 0) ans += now * 1;
            else if(a[vec[i][0]] == 1 && a[vec[i][1]] == 1) ans += now * 2;
            now *= 3;
        }
    }
    return unhash(ans);
}
// g++ -g -std=c++20 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run Anna.cpp Bruno.cpp grader.cpp

• Subtask 1: 100 / 100