QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291966 | #4820. Kitten's Computer | Radewoosh# | AC ✓ | 0ms | 3764kb | C++23 | 5.5kb | 2023-12-27 14:52:28 | 2023-12-27 14:52:29 |
Judging History
answer
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define shandom_ruffle random_shuffle
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1007;
const int d=400;
using ull=unsigned long long;
vector<pair<string,vi>> wyn;
ull regi[nax];
int czas[nax];
void wykonaj(string s, vi wek)
{
int x;
if (s[1]=='S')
{
x=wek.back();
wek.pop_back();
}
int naj=0;
for (int i : wek)
naj=max(naj, czas[i]);
naj++;
if (s=="SET")
regi[wek[0]]=regi[wek[1]];
if (s=="XOR")
regi[wek[0]]=regi[wek[1]]^regi[wek[2]];
if (s=="AND")
regi[wek[0]]=regi[wek[1]]®i[wek[2]];
if (s=="OR")
regi[wek[0]]=regi[wek[1]]|regi[wek[2]];
if (s=="NOT")
regi[wek[0]]=~regi[wek[1]];
if (s=="LSH")
regi[wek[0]]<<=x;
if (s=="RSH")
regi[wek[0]]>>=x;
czas[wek[0]]=max(czas[wek[0]], naj);
}
ull losuj()
{
ull ret=0;
for (int i=0; i<64; i++)
ret=(2*ret+(ull)(rand()&1));
return ret;
}
void test(ull x, ull y)
{
for (int i=1; i<=d; i++)
{
regi[i]=0;
czas[i]=0;
}
regi[1]=x;
regi[2]=y;
for (auto i : wyn)
wykonaj(i.first, i.second);
int naj=0;
for (int i=1; i<=d; i++)
naj=max(naj, czas[i]);
debug() << imie(naj) << imie(wyn.size());
}
int zawiera(vi wek, int v)
{
for (int i : wek)
if (i==v)
return 1;
return 0;
}
vi uzbieraj(vi wek, int ile=-1)
{
int r=wek.size();
if (ile==-1)
ile=r;
vi ret;
for (int i=130; (int)ret.size()<ile && i<=d; i++)
if (!zawiera(wek, i))
ret.push_back(i);
assert((int)ret.size()==ile);
return ret;
}
int main()
{
srand(time(0));
vi zbi;
{
for (int i=0; i<64; i++)
{
int x=3+5*i;
int y=x+1;
int xx=x+2;
int yy=y+2;
for (int j : {x, y})
{
wyn.push_back({"SET", {j, 1}});
wyn.push_back({"LSH", {j, 63-i}});
wyn.push_back({"RSH", {j, 63}});
}
for (int j=0; j<6; j++)
{
wyn.push_back({"LSH", {y, 1<<j}});
wyn.push_back({"OR", {xx, x, y}});
wyn.push_back({"OR", {yy, x, y}});
swap(x, xx);
swap(y, yy);
}
int z=3+5*i+4;
wyn.push_back({"SET", {z, 2}});
wyn.push_back({"LSH", {z, i}});
wyn.push_back({"AND", {x, x, z}});
zbi.push_back(x);
}
}
while((int)zbi.size()>2)
{
int r=zbi.size();
vi now=zbi;
zbi.clear();
vi pus=uzbieraj(now, 200);
while(r)
{
if (r%3)
{
zbi.push_back(now.back());
now.pop_back();
r--;
continue;
}
r-=3;
vi wek;
for (int i=0; i<3; i++)
{
wek.push_back(now.back());
now.pop_back();
}
int x=pus.back();
pus.pop_back();
int y=pus.back();
pus.pop_back();
vi faj;
for (int j=0; j<3; j++)
{
faj.push_back(pus.back());
pus.pop_back();
}
wyn.push_back({"XOR", {x, wek[0], wek[1]}});
wyn.push_back({"XOR", {x, x, wek[2]}});
for (int j=0; j<3; j++)
wyn.push_back({"AND", {faj[j], wek[j], wek[(j+1)%3]}});
wyn.push_back({"XOR", {y, faj[0], faj[1]}});
wyn.push_back({"XOR", {y, y, faj[2]}});
wyn.push_back({"LSH", {y, 1}});
zbi.push_back(x);
zbi.push_back(y);
}
}
debug() << imie(zbi);
wyn.push_back({"XOR", {400, zbi[0], zbi[1]}});
{
for (int i=1; i<=64; i++)
{
wyn.push_back({"XOR", {i, zbi[0], zbi[1]}});
wyn.push_back({"AND", {64+i, zbi[0], zbi[1]}});
if (i==64)
{
wyn.push_back({"XOR", {i, i, i}});
wyn.push_back({"XOR", {64+i, 64+i, 64+i}});
}
else
{
wyn.push_back({"LSH", {i, i}});
wyn.push_back({"LSH", {64+i, i}});
}
}
for (int i=1; i<=32; i<<=1)
{
for (int j=1; j<=64; j++)
{
if (!((j-1)&i))
{
wyn.push_back({"AND", {128+j, j, 64+j+i}});
wyn.push_back({"OR", {64+j, 64+j, 128+j}});
wyn.push_back({"AND", {j, j, j+i}});
}
}
}
}
wyn.push_back({"XOR", {1, 65, 400}});
for (auto i : wyn)
{
cout << i.first;
for (int j : i.second)
cout << " " << j;
cout << endl;
}
//~ ull x=losuj();
//~ ull y=losuj();
//~ debug() << imie(x*y);
//~ test(x, y);
//~ debug() << imie(regi[1]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
main
output:
SET 3 1 LSH 3 63 RSH 3 63 SET 4 1 LSH 4 63 RSH 4 63 LSH 4 1 OR 5 3 4 OR 6 3 4 LSH 6 2 OR 3 5 6 OR 4 5 6 LSH 4 4 OR 5 3 4 OR 6 3 4 LSH 6 8 OR 3 5 6 OR 4 5 6 LSH 4 16 OR 5 3 4 OR 6 3 4 LSH 6 32 OR 3 5 6 OR 4 5 6 SET 7 2 LSH 7 0 AND 3 3 7 SET 8 1 LSH 8 62 RSH 8 63 SET 9 1 LSH 9 62 RSH 9 63 LSH 9 1 OR 1...
result:
ok Correct: depth=69