QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291966#4820. Kitten's ComputerRadewoosh#AC ✓0ms3764kbC++235.5kb2023-12-27 14:52:282023-12-27 14:52:29

Judging History

你现在查看的是最新测评结果

  • [2023-12-27 14:52:29]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3764kb
  • [2023-12-27 14:52:28]
  • 提交

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]]&regi[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