답안 #444691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444691 2021-07-14T20:46:08 Z dolphingarlic 레지스터 (IOI21_registers) C++17
100 / 100
6 ms 1192 KB
#include "registers.h"
#include <bits/stdc++.h>




using namespace std;

using ll = long long;
using db = long double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;




template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T,SZ>;
template<class T> using PR = pair<T,T>;


template<class T> int lwb(V<T>& a, const T& b)
{
    return int(lower_bound(begin(a), end(a),b)-begin(a));
}


const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18;
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;



constexpr int pct(int x)
{
    return __builtin_popcount(x);
}
constexpr int bits(int x)
{
    return x == 0 ? 0 : 31-__builtin_clz(x);
}
constexpr int p2(int x)
{
    return 1<<x;
}
constexpr int msk2(int x)
{
    return p2(x)-1;
}

ll cdiv(ll a, ll b)
{
    return a/b+((a^b)>0&&a%b);
}
ll fdiv(ll a, ll b)
{
    return a/b-((a^b)<0&&a%b);
}

template<class T> bool ckmin(T& a, const T& b)
{
    return b < a ? a = b, 1 : 0;
}
template<class T> bool ckmax(T& a, const T& b)
{
    return a < b ? a = b, 1 : 0;
}

template<class T, class U> T fstTrue(T lo, T hi, U first)
{
    hi ++;
    assert(lo <= hi);
    while (lo < hi)
    {
        T mid = lo+(hi-lo)/2;
        first(mid) ? hi = mid : lo = mid+1;
    }
    return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U first)
{
    lo --;
    assert(lo <= hi);
    while (lo < hi)
    {
        T mid = lo+(hi-lo+1)/2;
        first(mid) ? lo = mid : hi = mid-1;
    }
    return lo;
}
template<class T> void remDup(vector<T>& v)
{
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)),end(v));
}
template<class T, class U> void erase(T& t, const U& u)
{
    auto it = t.find(u);
    assert(it != end(t));
    t.erase(it);
}



inline namespace Helpers
{



template<class T, class = void> struct is_iterable : false_type {};
template<class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
         decltype(end(declval<T>()))
         >
         > : true_type {};
template<class T> constexpr bool is_iterable_v = is_iterable<T>::value;


template<class T, class = void> struct is_readable : false_type {};
template<class T> struct is_readable<T,
             typename std::enable_if_t<
         is_same_v<decltype(cin >> declval<T&>()), istream&>
         >
         > : true_type {};
template<class T> constexpr bool is_readable_v = is_readable<T>::value;



template<class T, class = void> struct is_printable : false_type {};
template<class T> struct is_printable<T,
             typename std::enable_if_t<
         is_same_v<decltype(cout << declval<T>()), ostream&>
         >
         > : true_type {};
template<class T> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input
{
template<class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
template<class T, class ...U> void re(T& t, U&... u);
template<class T, class U> void re(pair<T,U>& p);


template<class T> typename enable_if<is_readable_v<T>,void>::type re(T& x)
{
    cin >> x;
}
template<class T> void re(complex<T>& c)
{
    T a,b;
    re(a,b);
    c = {a,b};
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i);
template<class T, class U> void re(pair<T,U>& p)
{
    re(p.first,p.second);
}
template<class T> typename enable_if<needs_input_v<T>,void>::type re(T& i)
{
    for (auto& x: i) re(x);
}
template<class T, class ...U> void re(T& t, U&... u)
{
    re(t);
    re(u...);
}


void rv(size_t) {}
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u);
template<class...U> void rv(size_t, size_t N2, U&... u);
template<class T, class ...U> void rv(size_t N, V<T>& t, U&... u)
{
    t.resize(N);
    re(t);
    rv(N,u...);
}
template<class...U> void rv(size_t, size_t N2, U&... u)
{
    rv(N2,u...);
}


void decrement() {}
template<class T, class ...U> void decrement(T& t, U&... u)
{
    --t;
    decrement(u...);
}


}

inline namespace ToString
{
template<class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;


template<class T> typename enable_if<is_printable_v<T>,str>::type ts(T v)
{
    stringstream ss;
    ss << fixed << setprecision(15) << v;
    return ss.str();
}
template<class T> str bit_vec(T t)
{
    str res = "{";
    for (int i = (0); i < (int((t).size())); ++i) res += ts(t[i]);
    res += "}";
    return res;
}
str ts(V<bool> v)
{
    return bit_vec(v);
}
template<size_t SZ> str ts(bitset<SZ> b)
{
    return bit_vec(b);
}
template<class T, class U> str ts(pair<T,U> p);
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v);
template<class T, class U> str ts(pair<T,U> p)
{
    return "("+ts(p.first)+", "+ts(p.second)+")";
}
template<class T> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep)
{

    bool fst = 1;
    str res = "";
    for (const auto& x: v)
    {
        if (!fst) res += sep;
        fst = 0;
        res += ts(x);
    }
    return res;
}
template<class T> typename enable_if<needs_output_v<T>,str>::type ts(T v)
{
    return "{"+ts_sep(v,", ")+"}";
}


template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
    return {ts(v)};
}
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type
ts_lev(const T& v)
{
    if (lev == 0 || !int((v).size())) return {ts(v)};
    vs res;
    for (const auto& t: v)
    {
        if (int((res).size())) res.back() += ",";
        vs tmp = ts_lev<lev-1>(t);
        res.insert(end(res),begin(tmp), end(tmp));
    }
    for (int i = (0); i < (int((res).size())); ++i)
    {
        str bef = " ";
        if (i == 0) bef = "{";
        res[i] = bef+res[i];
    }
    res.back() += "}";
    return res;
}
}

inline namespace Output
{
template<class T> void pr_sep(ostream& os, str, const T& t)
{
    os << ts(t);
}
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u)
{
    pr_sep(os,sep,t);
    os << sep;
    pr_sep(os,sep,u...);
}

template<class ...T> void pr(const T&... t)
{
    pr_sep(cout,"",t...);
}

void ps()
{
    cout << "\n";
}
template<class ...T> void ps(const T&... t)
{
    pr_sep(cout," ",t...);
    ps();
}

template<class ...T> void dbg_out(const T&... t)
{
    pr_sep(cerr," | ",t...);
    cerr << endl;
}
void loc_info(int line, str names)
{
    cerr << "Line(" << line << ") -> [" << names << "]: ";
}
template<int lev, class T> void dbgl_out(const T& t)
{
    cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl;
}


}

inline namespace FileIO
{
void setIn(str second)
{
    freopen(second.c_str(),"r",stdin);
}
void setOut(str second)
{
    freopen(second.c_str(),"w",stdout);
}
void setIO(str second = "")
{
    cin.tie(0)->sync_with_stdio(0);


    if (int((second).size())) setIn(second+".in"), setOut(second+".out");
}
}


void init_bits(int t, vi bits)
{
    vb v(2000);
    for (int i: bits) v.at(i) = 1;
    append_store(t, v);
}

void op_move(int t, int x)
{
    append_move(t,x);
}

void op_left(int t, int x, int second)
{
    append_left(t,x,second);
}

void op_and(int t, int x, int y)
{
    append_and(t,x,y);
}

void op_or(int t, int x, int y)
{
    append_or(t,x,y);
}

void op_xor(int t, int x, int y)
{
    append_xor(t,x,y);
}

void op_add(int t, int x, int y)
{
    append_add(t,x,y);
}


void op_not(int t, int x)
{
    append_not(t,x);
}

void op_right(int t, int x, int second)
{
    append_right(t,x,second);
}

vi num_bits(int x)
{
    vi ans;
    for (int i = (0); i < (x); ++i) ans.push_back(i);
    return ans;
}

void construct_instructions(int second, int n, int k, int q)
{
    int p = 1;
    if (second == 0)
    {
        while (p < n) p *= 2;
        {
            vi rel;
            for (int i = (n); i < (p); ++i) for (int j = (0); j < (k); ++j) rel.push_back(i*k+j);
            init_bits(1,rel);
            op_or(0,0,1);
            n = p;
        }

        int tot = n*k;
        vi all_bits;
        for (int i = (0); i < (tot); ++i) all_bits.push_back(i);
        init_bits(20,all_bits);
        init_bits(21, {0});
        for (int len = k; len < tot; len *= 2)
        {
            vi a,b;
            for (int i = (0); i < (tot); ++i)
            {
                if (i%(2*len) < len) a.push_back(i);
                else b.push_back(i);
            }
            init_bits(1,a);

            op_and(3,1,0);
            op_right(4,0,len);



            op_not(5,4);
            op_and(5,5,1);
            op_add(6,3,5);


            vi rel;
            for (int i = len; i < tot; i += 2*len) rel.push_back(i);
            init_bits(7,rel);
            op_and(6,6,7);
            op_right(7,6,len);
            op_not(7,7);
            op_add(6,6,7);
            op_add(6,6,21);


            op_xor(7,6,20);
            op_and(3,3,7);
            op_and(4,4,6);
            op_or(0,3,4);
        }
    }
    else
    {
        p = n;
        if (p&1) ++p;
        {
            vi rel;
            for (int i = (n); i < (p); ++i) for (int j = (0); j < (k); ++j) rel.push_back(i*k+j);
            init_bits(1,rel);
            op_or(0,0,1);
            n = p;
        }
        int tot = n*k;
        vi all_bits;
        for (int i = (0); i < (tot); ++i) all_bits.push_back(i);
        init_bits(20,all_bits);
        init_bits(21, {0});
        init_bits(40,num_bits(k));

        append_print(0);
        for (int it = (0); it < (105); ++it)
        {
            auto tran = [&]()
            {
                int len = k;
                vi a,b;
                for (int i = (0); i < (tot); ++i)
                {
                    if (i%(2*len) < len) a.push_back(i);
                    else b.push_back(i);
                }
                init_bits(1,a);

                op_and(3,1,0);
                op_right(4,0,len);
                op_and(4,4,1);


                op_not(5,4);
                op_and(5,5,1);
                op_add(6,3,5);


                vi rel;
                for (int i = len; i < tot; i += 2*len) rel.push_back(i);
                init_bits(7,rel);
                op_and(6,6,7);
                op_right(7,6,len);
                op_not(7,7);
                op_add(6,6,7);
                op_add(6,6,21);


                op_xor(7,6,20);
                op_and(12,3,7);
                op_and(13,4,6);
                op_or(0,12,13);


                op_and(8,3,6);
                op_and(9,4,7);
                op_or(8,8,9);
                op_left(8,8,len);
                op_or(0,0,8);


            };


            if (it%2 == 0)
            {
                tran();
            }
            else
            {
                assert(n == p);
                op_move(50,0);

                op_and(50,50,40);
                op_right(0,0,k);
                {
                    vi rel;
                    for (int j = (0); j < (k); ++j) rel.push_back((n-1)*k+j);

                    init_bits(80,rel);
                    op_or(0,0,80);


                }
                append_print(0);
                tran();
                append_print(0);
                op_left(0,0,k);
                op_and(0,0,20);
                op_or(0,0,50);
            }
            append_print(0);
            append_print(10);
        }
    }


}

Compilation message

registers.cpp: In function 'void FileIO::setIn(str)':
registers.cpp:338:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  338 |     freopen(second.c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
registers.cpp: In function 'void FileIO::setOut(str)':
registers.cpp:342:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  342 |     freopen(second.c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1188 KB Output is correct
2 Correct 5 ms 1184 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1188 KB Output is correct
2 Correct 5 ms 1184 KB Output is correct
3 Correct 6 ms 1192 KB Output is correct
4 Correct 5 ms 1184 KB Output is correct
5 Correct 6 ms 1192 KB Output is correct
6 Correct 5 ms 1192 KB Output is correct
7 Correct 5 ms 1192 KB Output is correct