#include"Alice.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace A{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u;
vector<pair<int,int>> p;
void link(ll x,ll y,ll z)
{
ll i;
for(i=y;i<=z;i++)
{
perm[i]=x;
if(adj[x][i]==0)
{
adj[x][i]=1;
adj[i][x]=1;
}
}
}
pair<ll,ll> f(ll x,ll y)
{
//printf("%lld(%lld)\n",ll(x),y);
c[x]=1;
ll i,mn=100000,mx=0;
pair<ll,ll> p;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
p=f(v[x][i],x);
mn=min(mn,p.first);
mx=max(mx,p.second);
}
if(h[x]<=1)
{
mn=min(mn,x);
mx=max(mx,x);
}
return {mn,mx};
}
void Clear()
{
ll i;
for(i=1;i<=4991;i++)
{
v[i].clear();
h[i]=0;
b[i]=0;
a[i]=0;
c[i]=0;
d[i]=0;
perm[i]=0;
}
for(i=1;i<=4991;i++)
for(j=1;j<=4991;j++)
{
adj[i][j]=0;
}
}
vector<pair<int,int>> Alice()
{
for(i=1;i<=4991;i++)
adj[i][i]=1;
k=setN(4991);
i=1;
while(k>0)
{
a[i]=k%mod;
k/=mod;
i++;
}
for(i=1;i<=31;i++)
{
x=i;
j=1;
while(x>0)
{
if(x&1)
{
b[i]^=a[j];
}
x>>=1;
j++;
}
b[i]++;
}
for(i=1;i<=31;i++)
{
if(i!=31)
link(b[i],(i-1)*161+1,i*161);
else
{
link(b[i],(i-1)*161+1,4991);
}
}
n=4991;
for(i=1;i<=n;i++)
{
if(c[i]==2)
continue;
x=i;
y=0;
while(1)
{
c[x]=1;
y=x;
x=perm[x];
if(c[x]==2)
break;
if(c[x]==1)
{
if(x==y)
break;
adj[x][y]=0;
adj[y][x]=0;
break;
}
}
x=i;
while(1)
{
if(c[x]==2)
break;
c[x]=2;
x=perm[x];
}
}
for(i=1;i<=n;i++)
{
c[i]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(adj[i][j]==1)
{
v[i].push_back(j);
v[j].push_back(i);
h[i]++;
h[j]++;
p.push_back({i,j});
}
}
}
for(i=1;i<=n;i++)
{
if(c[i]==0)
{
u.push_back(f(i,0));
}
}
for(i=0;i<u.size()-1;i++)
{
x=u[i].first;
y=u[i+1].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
p.push_back({x,y});
}
return p;
}
};
vector<pair<int,int>> Alice()
{
return A::Alice();
}
#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace B{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u,p;
void link(ll x,ll y,ll z)
{
ll i;
for(i=y;i<=z;i++)
{
perm[i]=x;
if(adj[x][i]==0)
{
adj[x][i]=1;
adj[i][x]=1;
}
}
}
pair<ll,ll> f(ll x,ll y)
{
//printf("%lld(%lld)\n",ll(x),y);
c[x]=1;
ll i,mn=100000,mx=0;
pair<ll,ll> p;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
p=f(v[x][i],x);
mn=min(mn,p.first);
mx=max(mx,p.second);
}
if(h[x]<=1)
{
mn=min(mn,x);
mx=max(mx,x);
}
return {mn,mx};
}
void Clear()
{
ll i;
for(i=1;i<=4991;i++)
{
v[i].clear();
h[i]=0;
b[i]=0;
a[i]=0;
c[i]=0;
d[i]=0;
perm[i]=0;
}
for(i=1;i<=4991;i++)
for(j=1;j<=4991;j++)
{
adj[i][j]=0;
}
}
ll Bob(vector<pair<int,int>> V)
{
Clear();
m=V.size();
for(i=1;i<=m;i++)
{
x=V[i-1].first;
y=V[i-1].second;
v[x].push_back(y);
v[y].push_back(x);
h[x]++;
h[y]++;
}
n=4991;
for(e=1;e<=31;e++)
{
if(e!=31)
{
l=(e-1)*161+1;
r=e*161;
}
else
{
l=(e-1)*161+1;
r=4991;
}
for(i=1;i<=n;i++)
{
if(h[i]>=2)
{
//printf("(%lld)\n",i);
s=0;
for(j=0;j<h[i];j++)
{
if(l<=v[i][j]&&r>=v[i][j])
s++;
}
if(s>=2)
{
b[e]=i-1;
//printf("%lld %lld\n",e,i-1);
break;
}
}
if(i==n)
{
b[e]=-1;
}
}
}
b[0]=0;
d[1]=1;
d[2]=2;
d[4]=3;
d[8]=4;
d[16]=5;
for(i=0;i<=31;i++)
{
for(j=0;j<=31;j++)
{
if((i|j)==j&&d[(j-i)]!=0)
{
if(b[i]!=-1&&b[j]!=-1)
{
a[d[j-i]]=b[i]^b[j];
}
}
}
}
s=0;
for(i=5;i>=1;i--)
{
s=s*mod+a[i];
}
return s;
}
};
ll Bob(vector<pair<int,int>> V)
{
return B::Bob(V);
}
Compilation message
Alice.cpp: In function 'std::vector<std::pair<int, int> > A::Alice()':
Alice.cpp:157:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(i=0;i<u.size()-1;i++)
| ~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
307152 KB |
Correct. |
2 |
Correct |
118 ms |
307196 KB |
Correct. |
3 |
Correct |
115 ms |
307296 KB |
Correct. |
4 |
Correct |
136 ms |
307152 KB |
Correct. |
5 |
Correct |
128 ms |
307056 KB |
Correct. |
6 |
Correct |
122 ms |
307268 KB |
Correct. |
7 |
Correct |
121 ms |
307208 KB |
Correct. |
8 |
Correct |
126 ms |
307088 KB |
Correct. |
9 |
Correct |
120 ms |
307132 KB |
Correct. |
10 |
Correct |
122 ms |
307164 KB |
Correct. |
11 |
Correct |
134 ms |
307252 KB |
Correct. |
12 |
Correct |
122 ms |
307156 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
307152 KB |
Correct. |
2 |
Correct |
118 ms |
307196 KB |
Correct. |
3 |
Correct |
115 ms |
307296 KB |
Correct. |
4 |
Correct |
136 ms |
307152 KB |
Correct. |
5 |
Correct |
128 ms |
307056 KB |
Correct. |
6 |
Correct |
122 ms |
307268 KB |
Correct. |
7 |
Correct |
121 ms |
307208 KB |
Correct. |
8 |
Correct |
126 ms |
307088 KB |
Correct. |
9 |
Correct |
120 ms |
307132 KB |
Correct. |
10 |
Correct |
122 ms |
307164 KB |
Correct. |
11 |
Correct |
134 ms |
307252 KB |
Correct. |
12 |
Correct |
122 ms |
307156 KB |
Correct. |
13 |
Correct |
124 ms |
306920 KB |
Correct. |
14 |
Correct |
120 ms |
307184 KB |
Correct. |
15 |
Correct |
122 ms |
307100 KB |
Correct. |
16 |
Correct |
127 ms |
307260 KB |
Correct. |
17 |
Correct |
137 ms |
307164 KB |
Correct. |
18 |
Correct |
133 ms |
306992 KB |
Correct. |
19 |
Correct |
125 ms |
307024 KB |
Correct. |
20 |
Correct |
125 ms |
307064 KB |
Correct. |
21 |
Correct |
129 ms |
307156 KB |
Correct. |
22 |
Correct |
135 ms |
307172 KB |
Correct. |
23 |
Correct |
123 ms |
306904 KB |
Correct. |
24 |
Correct |
120 ms |
307052 KB |
Correct. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
307152 KB |
Correct. |
2 |
Correct |
118 ms |
307196 KB |
Correct. |
3 |
Correct |
115 ms |
307296 KB |
Correct. |
4 |
Correct |
136 ms |
307152 KB |
Correct. |
5 |
Correct |
128 ms |
307056 KB |
Correct. |
6 |
Correct |
122 ms |
307268 KB |
Correct. |
7 |
Correct |
121 ms |
307208 KB |
Correct. |
8 |
Correct |
126 ms |
307088 KB |
Correct. |
9 |
Correct |
120 ms |
307132 KB |
Correct. |
10 |
Correct |
122 ms |
307164 KB |
Correct. |
11 |
Correct |
134 ms |
307252 KB |
Correct. |
12 |
Correct |
122 ms |
307156 KB |
Correct. |
13 |
Correct |
124 ms |
306920 KB |
Correct. |
14 |
Correct |
120 ms |
307184 KB |
Correct. |
15 |
Correct |
122 ms |
307100 KB |
Correct. |
16 |
Correct |
127 ms |
307260 KB |
Correct. |
17 |
Correct |
137 ms |
307164 KB |
Correct. |
18 |
Correct |
133 ms |
306992 KB |
Correct. |
19 |
Correct |
125 ms |
307024 KB |
Correct. |
20 |
Correct |
125 ms |
307064 KB |
Correct. |
21 |
Correct |
129 ms |
307156 KB |
Correct. |
22 |
Correct |
135 ms |
307172 KB |
Correct. |
23 |
Correct |
123 ms |
306904 KB |
Correct. |
24 |
Correct |
120 ms |
307052 KB |
Correct. |
25 |
Correct |
134 ms |
306396 KB |
Correct. |
26 |
Correct |
135 ms |
307136 KB |
Correct. |
27 |
Correct |
127 ms |
306900 KB |
Correct. |
28 |
Correct |
127 ms |
306896 KB |
Correct. |
29 |
Correct |
124 ms |
307156 KB |
Correct. |
30 |
Correct |
120 ms |
305572 KB |
Correct. |
31 |
Correct |
140 ms |
306660 KB |
Correct. |
32 |
Correct |
123 ms |
337020 KB |
Correct. |
33 |
Correct |
139 ms |
335572 KB |
Correct. |
34 |
Correct |
121 ms |
335320 KB |
Correct. |
35 |
Correct |
134 ms |
336612 KB |
Correct. |
36 |
Correct |
122 ms |
335004 KB |
Correct. |
37 |
Correct |
122 ms |
335640 KB |
Correct. |
38 |
Correct |
120 ms |
335856 KB |
Correct. |
39 |
Correct |
120 ms |
334548 KB |
Correct. |
40 |
Correct |
123 ms |
336456 KB |
Correct. |
41 |
Correct |
120 ms |
336604 KB |
Correct. |
42 |
Correct |
120 ms |
336512 KB |
Correct. |
43 |
Correct |
123 ms |
335204 KB |
Correct. |
44 |
Correct |
125 ms |
335068 KB |
Correct. |