oj.uz

Submission #110818

# Submission time Handle Problem Language Result Execution time Memory
110818 2019-05-12T09:52:28 Z zscoder None (JOI16_memory2) C++17
100 / 100
 4 ms 896 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 816 KB Output is correct
8 Correct 4 ms 896 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 3 ms 796 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 768 KB Output is correct