oj.uz

답안 #147849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147849 2019-08-31T02:17:10 Z zscoder(#3674, zscoder) 백점을 받아랏! (FXCUP4_hundred) C++17
100 / 100
 10 ms 432 KB 
#include "hundred.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<int> 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;

string ori;
int ans[111][3];
int cnt[3];

map<string,int> ma;

int query(string s)
{	
	if(ma.find(s)!=ma.end()) return ma[s];
	return (ma[s]=Mark(s));	
}

vector<string> rem;

bool cmp(pair<char,int> a, pair<char,int> b)
{
	return a.se<b.se;
}

int swp(int p1, int p2)
{
	int be = query(ori);
	swap(ori[p1],ori[p2]);
	int af = query(ori);
	swap(ori[p1],ori[p2]);
	return (af-be);
}

int rs(int p1, int p2, string &ans)
{
	int as = 0;
	if(ori[p1]==ans[p1]) as--;
	if(ori[p2]==ans[p2]) as--;
	if(ori[p2]==ans[p1]) as++;
	if(ori[p1]==ans[p2]) as++;
	return as;
}

vi pos[3];

bool check(string &ss)
{
	int rr[3]={0,0,0};
	for(int i=0;i<ss.length();i++)
	{
		if(ss[i]!='?')
		{
			rr[ss[i]-'A']++;
			if(rr[ss[i]-'A']>cnt[ss[i]-'A']) return false;
		}
	}
	return true;
}

std::string GetHundredPoints(int A, int B, int C) 
{
	//write some "auto-checker" for ez life
	cnt[0]=A; cnt[1]=B; cnt[2]=C;
	int n=100;
	for(int i=0;i<n;i++)
	{
		ans[i][0]=ans[i][1]=ans[i][2]=1;
	}
	for(int j=0;j<3;j++)
	{
		for(int i=0;i<cnt[j];i++)
		{
			ori+=char('A'+j);
		}
	}
	srand(1203917);
	random_shuffle(ori.begin(),ori.end());
	vector<pair<char,int> > vv;
	for(int i=0;i<3;i++)
	{
		vv.pb({'A'+i,cnt[i]});
	}
	sort(vv.begin(),vv.end(),cmp);
	int M[3]={0,0,0};
	for(int i=0;i<3;i++)
	{
		M[vv[i].fi-'A']=i;
	}
	for(int i=0;i<n;i++)
	{
		pos[M[ori[i]-'A']].pb(i);
	}
	if(vv[0].se==0)
	{
		string tmp = "";
		for(int i=0;i<n;i++) tmp+="?";
		if(vv[1].se==0)
		{
			string res="";
			for(int i=0;i<n;i++) res+=vv[2].fi;
			return res;
		}
		for(int j=1;j<3;j++)
		{
			tmp[pos[1][0]]=vv[j].fi;
			rem.pb(tmp);
		}
		for(int v:pos[2])
		{
			int sp = swp(pos[1][0],v);
			for(string &r:rem)
			{
				if(r=="") continue;
				int ps=-1;
				for(int j=1;j<3;j++)
				{
					r[v]=vv[j].fi;
					if(!check(r)) 
					{
						continue;
					}
					if(rs(pos[1][0],v,r)==sp)
					{
						ps=j; break;
					}
				}
				if(ps==-1) r="";
				else r[v]=vv[ps].fi;
			}
		}
		for(int v:pos[1])
		{
			int sp = swp(pos[2][0],v);
			for(string &r:rem)
			{
				if(r=="") continue;
				int ps=-1;
				for(int j=1;j<3;j++)
				{
					r[v]=vv[j].fi;
					if(!check(r)) 
					{
						continue;
					}
					if(rs(pos[2][0],v,r)==sp)
					{
						ps=j; break;
					}
				}
				if(ps==-1) r="";
				else r[v]=vv[ps].fi;
			}
		}
		for(string R:rem)
		{
			if(R.length()>0) return R;
		}
	}
	else
	{
		string tmp = "";
		for(int i=0;i<n;i++) tmp+="?";
		for(int j=0;j<3;j++)
		{
			tmp[pos[0][0]]=vv[j].fi;
			rem.pb(tmp);
		}
		for(int v:pos[1])
		{
			int sp = swp(pos[0][0],v);
			for(string &r:rem)
			{
				if(r=="") continue;
				int ps=-1;
				for(int j=0;j<3;j++)
				{
					r[v]=vv[j].fi;
					if(!check(r)) 
					{
						continue;
					}
					if(rs(pos[0][0],v,r)==sp)
					{
						ps=j; break;
					}
				}
				if(ps==-1) r="";
				else r[v]=vv[ps].fi;
			}
		}
		for(int v:pos[2])
		{
			int sp = swp(pos[0][0],v);
			for(string &r:rem)
			{
				if(r=="") continue;
				int ps=-1;
				for(int j=0;j<3;j++)
				{
					r[v]=vv[j].fi;
					if(!check(r)) 
					{
						continue;
					}
					if(rs(pos[0][0],v,r)==sp)
					{
						ps=j; break;
					}
				}
				if(ps==-1) r="";
				else r[v]=vv[ps].fi;
			}
		}
		for(int v:pos[0])
		{
			int sp = swp(pos[1][0],v);
			for(string &r:rem)
			{
				if(r=="") continue;
				int ps=-1;
				for(int j=0;j<3;j++)
				{
					r[v]=vv[j].fi;
					if(!check(r)) 
					{
						continue;
					}
					if(rs(pos[1][0],v,r)==sp)
					{
						ps=j; break;
					}
				}
				if(ps==-1) r="";
				else r[v]=vv[ps].fi;
			}
		}
		for(string R:rem)
		{
			if(R.length()>0&&check(R)) return R;
		}
	}
}

Compilation message

hundred.cpp: In function 'bool check(std::__cxx11::string&)':
hundred.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ss.length();i++)
              ~^~~~~~~~~~~~
hundred.cpp: In function 'std::__cxx11::string GetHundredPoints(int, int, int)':
hundred.cpp:257:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 388 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 432 KB Output is correct
4 Correct 8 ms 432 KB Output is correct
5 Correct 9 ms 384 KB Output is correct

Subtask #2
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 388 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 432 KB Output is correct
4 Correct 8 ms 432 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 396 KB Output is correct
8 Correct 7 ms 344 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 6 ms 304 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 7 ms 352 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 7 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct