oj.uz

Submission #147573

# Submission time Handle Problem Language Result Execution time Memory
147573 2019-08-30T06:31:57 Z mohammedehab2002 Broken Device (JOI17_broken_device) C++11
100 / 100
 1825 ms 3880 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
int ans[155],pos[128];
bitset<129> mat[128],bas[128];
void add(int r)
{
	for (int i=0;i<128;i++)
	{
		if (mat[r][i])
		mat[r]^=bas[i];
	}
	for (int i=0;i<128;i++)
	{
		if (mat[r][i])
		{
			bas[i]=mat[r];
			pos[r]=i;
			return;
		}
	}
}
void Anna(int n,long long x,int k,int p[])
{
	/*for (int i=0;i<128;i++)
	mat[i].reset();
	mat[0][0]=1;
	for (int i=1;i<8;i++)
	{
		int len=(1<<(i-1));
		for (int j=0;j<len;j++)
		{
			for (int l=0;l<len;l++)
			{
				mat[j+len][l]=mat[j][l];
				mat[j][l+len]=mat[j][l];
			}
		}
	}*/
	mt19937 rng(159181);
	for (int i=0;i<128;i++)
	{
		for (int j=0;j<128;j++)
		mat[i][j]=uniform_int_distribution<int>(0,1)(rng);
	}
	for (int i=0;i<128;i++)
	{
		bas[i].reset();
		for (int j=0;j<k;j++)
		mat[i][p[j]]=0;
	}
	memset(pos,-1,sizeof(pos));
	memset(ans,-1,sizeof(ans));
	for (int i=0;i<128;i++)
	{
		if (i<60)
		{
			bool b=(x&(1LL<<i));
			mat[i][128]=b;
		}
		else
		mat[i][128]=0;
		add(i);
	}
	for (int i=127;i>=0;i--)
	{
		if (pos[i]==-1)
		continue;
		for (int j=0;j<i;j++)
		{
			if (mat[j][pos[i]])
			mat[j]^=mat[i];
		}
	}
	for (int i=0;i<128;i++)
	{
		if (pos[i]!=-1)
		ans[pos[i]]=mat[i][128];
	}
	for (int i=0;i<n;i++)
	{
		if (ans[i]==-1)
		ans[i]=0;
		Set(i,ans[i]);
	}
}
#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
bitset<128> hmat[128];
long long Bruno(int n,int a[])
{
	/*hmat[0][0]=1;
	for (int i=1;i<8;i++)
	{
		int len=(1<<(i-1));
		for (int j=0;j<len;j++)
		{
			for (int l=0;l<len;l++)
			{
				hmat[j+len][l]=hmat[j][l];
				hmat[j][l+len]=hmat[j][l];
			}
		}
	}*/
	mt19937 rng(159181);
	for (int i=0;i<128;i++)
	{
		for (int j=0;j<128;j++)
		hmat[i][j]=uniform_int_distribution<int>(0,1)(rng);
	}
	long long x=0;
	for (int i=0;i<60;i++)
	{
		long long cur=0;
		for (int j=0;j<n;j++)
		{
			if (hmat[i][j])
			cur^=a[j];
		}
		x|=(cur<<i);
	}
	return x;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 3880 KB Output is correct - L* = 40
2 Correct 1764 ms 3328 KB Output is correct - L* = 40
3 Correct 1757 ms 3320 KB Output is correct - L* = 40
4 Correct 1758 ms 3136 KB Output is correct - L* = 40
5 Correct 1763 ms 3312 KB Output is correct - L* = 40
6 Correct 1758 ms 3312 KB Output is correct - L* = 40
7 Correct 1775 ms 3712 KB Output is correct - L* = 40
8 Correct 1756 ms 3464 KB Output is correct - L* = 40
9 Correct 1763 ms 3256 KB Output is correct - L* = 40
10 Correct 1759 ms 3440 KB Output is correct - L* = 40
11 Correct 1763 ms 3376 KB Output is correct - L* = 40
12 Correct 1759 ms 3312 KB Output is correct - L* = 40
13 Correct 1758 ms 3096 KB Output is correct - L* = 40
14 Correct 1777 ms 3328 KB Output is correct - L* = 40
15 Correct 1767 ms 3600 KB Output is correct - L* = 40
16 Correct 1757 ms 3312 KB Output is correct - L* = 40
17 Correct 1771 ms 3312 KB Output is correct - L* = 40
18 Correct 1762 ms 3312 KB Output is correct - L* = 40
19 Correct 1774 ms 3552 KB Output is correct - L* = 40
20 Correct 1756 ms 3456 KB Output is correct - L* = 40
21 Correct 1763 ms 3568 KB Output is correct - L* = 40
22 Correct 1763 ms 3512 KB Output is correct - L* = 40
23 Correct 1755 ms 3320 KB Output is correct - L* = 40
24 Correct 1760 ms 3360 KB Output is correct - L* = 40
25 Correct 1758 ms 3312 KB Output is correct - L* = 40
26 Correct 1755 ms 3408 KB Output is correct - L* = 40
27 Correct 1757 ms 3624 KB Output is correct - L* = 40
28 Correct 1757 ms 3392 KB Output is correct - L* = 40
29 Correct 1772 ms 3320 KB Output is correct - L* = 40
30 Correct 1763 ms 3560 KB Output is correct - L* = 40
31 Correct 1825 ms 3304 KB Output is correct - L* = 40
32 Correct 1767 ms 3512 KB Output is correct - L* = 40
33 Correct 1759 ms 3152 KB Output is correct - L* = 40
34 Correct 1773 ms 3568 KB Output is correct - L* = 40
35 Correct 1756 ms 3312 KB Output is correct - L* = 40
36 Correct 1775 ms 3168 KB Output is correct - L* = 40
37 Correct 1757 ms 3136 KB Output is correct - L* = 40
38 Correct 1770 ms 3400 KB Output is correct - L* = 40
39 Correct 1779 ms 3616 KB Output is correct - L* = 40
40 Correct 1763 ms 3288 KB Output is correct - L* = 40