Submission #110818

#	Time	Username	Problem	Language	Result	Execution time	Memory
110818		zscoder	Memory 2 (JOI16_memory2)	C++17	100 / 100	4 ms	896 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int dp[333][333];

int ask(int u, int v)
{
	assert(u!=v);
	if(dp[u][v]!=-1) return dp[u][v];
	else return (dp[u][v]=dp[v][u]=Flip(u,v));
}

int ans[333];
int cnt[1111];
map<int,int> ma;

void triquery(int a, int b, int c)
{
	int x = ask(a,b);
	int y = ask(a,c);
	int z = ask(b,c);
	//cerr<<x<<' '<<y<<' '<<z<<' '<<ma.size()<<endl;
	if(x==y&&y==z&&x==z) return ;
	if(x==y)
	{
		ans[a]=x; cnt[x]++;
		ma[x]--;
		if(ma[x]==0) ma.erase(x);
	}
	if(x==z)
	{
		ans[b]=x; cnt[x]++;
		ma[x]--;
		if(ma[x]==0) ma.erase(x);
	}
	if(y==z)
	{
		ans[c]=y; cnt[y]++;
		ma[y]--;
		if(ma[y]==0) ma.erase(y);
	}
}
void Solve(int T, int N)
{
	memset(dp,-1,sizeof(dp));
	int n=N;
	memset(ans,-1,sizeof(ans));
	for(int i=0;i<n;i++) ma[i]=2;
	while(ma.size()>=3)
	{
		vi vec;
		for(int i=0;i<2*n;i++)
		{
			if(ans[i]==-1)
			{
				vec.pb(i);
			}
		}
		random_shuffle(vec.begin(),vec.end());
		triquery(vec[0],vec[1],vec[2]);
	}
	vi rem;
	for(int i=0;i<n;i++)
	{
		if(cnt[i]<2) rem.pb(i);
	}
	vi vec;
	for(int i=0;i<2*n;i++)
	{
		if(ans[i]==-1)
		{
			vec.pb(i);
		}
	}
	map<int,int> freq;
	for(int i=0;i<vec.size();i++)
	{
		for(int j=i+1;j<vec.size();j++)
		{
			freq[ask(vec[i],vec[j])]++;
		}
	}
	if(ma.size()==1)
	{
		for(int v:vec) ans[v]=rem[0];
	}
	else
	{
		vector<ii> V;
		for(int r:rem) V.pb({freq[r],r});
		sort(V.begin(),V.end());
		int a = V[0].se; int b = V[1].se;
		if(cnt[a]==0)
		{
			for(int i=0;i<vec.size();i++)
			{
				for(int j=i+1;j<vec.size();j++)
				{
					if(ask(vec[i],vec[j])==a)
					{
						ans[vec[i]]=ans[vec[j]]=a;
					}
				}
			}
		}
		else
		{
			int otherpos=-1;
			for(int i=0;i<2*n;i++)
			{
				if(ans[i]==a) otherpos=i;
			}
			for(int v:vec)
			{
				if(ask(v,otherpos)==a)
				{
					ans[v]=a;
				}
			}
		}
		for(int i=0;i<2*n;i++)
		{
			if(ans[i]==-1) ans[i]=b;
		}
	}
	vi F[111];
	for(int i=0;i<2*n;i++)
	{
		F[ans[i]].pb(i);
	}
	for(int i=0;i<n;i++)
	{
		Answer(F[i][0],F[i][1],i);
	}
}

Compilation message (stderr)

memory2.cpp: In function 'void Solve(int, int)':
memory2.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
memory2.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<vec.size();j++)
                 ~^~~~~~~~~~~
memory2.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<vec.size();i++)
                ~^~~~~~~~~~~
memory2.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=i+1;j<vec.size();j++)
                   ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 50 / 50
• Subtask 3: 40 / 40