QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #282695 | #2894. 麻将模拟器 | qkm66666 | WA | 76ms | 3712kb | C++14 | 9.7kb | 2023-12-12 19:51:46 | 2023-12-12 19:51:46 |
Judging History
answer
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<random>
#include<ctime>
#include<queue>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FF fflush(stdout)
#define inf 0x3f3f3f3f
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int s=0,f=1;
char x=getchar();
while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();
while(isdigit(x))s=s*10+x-'0',x=getchar();
return s*f;
}
const int p=1e9+7;
//ll ksm(int a,int b){ll ans=1,bs=a;while(b){if(b&1)ans=ans*bs%p;bs=bs*bs%p;b>>=1;}return ans;}
mt19937 rd(time(0));
#define reaD read
int c[555];
int cur[555];
int ans;
bool ok=1;
void era(vector<int> &a,int x)
{
for(int i=0;i<a.size();i++)
{
if(a[i]==x)
{
a.erase(a.begin()+i);
break;
}
}
}
void dfs(vector<int> a,int s,int d,int cs)
{
if(cs>=ans)return ;
ans=min(ans,cs+s*3);
if(s==0)
{
// ans=min(ans,cs);
return ;
}
for(int i=d;i<a.size();i++)
if(i==a.size()-1||a[i]!=a[i+1])
{
if(a[i]>500)return ;
vector<int> tmp=a;
if(a[i]<400&&cur[a[i]+1]&&cur[a[i]+2])
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]+1);
era(tmp,a[i]+2);
cur[a[i]]--;
cur[a[i]+2]--;
cur[a[i]+1]--;
dfs(tmp,s-1,i,cs);
cur[a[i]]++;
cur[a[i]+2]++;
cur[a[i]+1]++;
}
if(cur[a[i]]>=3)
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]);
era(tmp,a[i]);
cur[a[i]]-=3;
dfs(tmp,s-1,i,cs);
cur[a[i]]+=3;
}
if(cur[a[i]]==2&&c[a[i]]<=3)
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]);
cur[a[i]]-=2;
c[a[i]]++;
dfs(tmp,s-1,i,cs+1);
c[a[i]]--;
cur[a[i]]+=2;
}
if(a[i]<400&&cur[a[i]+1])
{
if(a[i]%10<=7&&c[a[i]+2]<=3&&!cur[a[i]+2])
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]+1);
cur[a[i]]--;
cur[a[i]+1]--;
c[a[i]+2]++;
dfs(tmp,s-1,i,cs+1);
cur[a[i]]++;
cur[a[i]+1]++;
c[a[i]+2]--;
}
if(a[i]%10<=8&&a[i]%10>=2&&c[a[i]-1]<=3&&!cur[a[i]-1])
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]+1);
cur[a[i]]--;
cur[a[i]+1]--;
c[a[i]-1]++;
dfs(tmp,s-1,i,cs+1);
cur[a[i]]++;
cur[a[i]+1]++;
c[a[i]-1]--;
}
}
if(a[i]<400&&cur[a[i]+2])
{
if(c[a[i]+1]<=3&&!cur[a[i]+1])
{
tmp=a;
era(tmp,a[i]);
era(tmp,a[i]+2);
cur[a[i]]--;
cur[a[i]+2]--;
c[a[i]+1]++;
dfs(tmp,s-1,i,cs+1);
cur[a[i]]++;
cur[a[i]+2]++;
c[a[i]+1]--;
}
}
era(tmp,a[i]);
if(c[a[i]]<=2&&cur[a[i]]==1)
cur[a[i]]--,c[a[i]]+=2,dfs(tmp,s-1,i,cs+2),c[a[i]]-=2,cur[a[i]]++;
if(a[i]<400&&a[i]%10<=7&&c[a[i]+1]<=3&&c[a[i]+2]<=3&&!cur[a[i]+1]&&!cur[a[i]+2])
cur[a[i]]--,c[a[i]+1]++,c[a[i]+2]++,dfs(tmp,s-1,i,cs+2),c[a[i]+1]--,c[a[i]+2]--,cur[a[i]]++;
if(a[i]<400&&a[i]%10<=8&&a[i]%10>=2&&c[a[i]-1]<=3&&c[a[i]+1]<=3&&!cur[a[i]-1]&&!cur[a[i]+1])
cur[a[i]]--,c[a[i]-1]++,c[a[i]+1]++,dfs(tmp,s-1,i,cs+2),c[a[i]-1]--,c[a[i]+1]--,cur[a[i]]++;
if(a[i]<400&&a[i]%10>=3&&c[a[i]-1]<=3&&c[a[i]-2]<=3&&!cur[a[i]-1]&&!cur[a[i]-2])
cur[a[i]]--,c[a[i]-1]++,c[a[i]-2]++,dfs(tmp,s-1,i,cs+2),c[a[i]-1]--,c[a[i]-2]--,cur[a[i]]++;
}
}
int cal(vector<int> a)
{
for(auto i:a)c[i]++,cur[i]++;
ans=a.size()/3*2+1;
for(int i=0;i<a.size();i++)
if(i==0||a[i]!=a[i-1])
{
vector<int> tmp=a;
if(cur[a[i]]>=2)
{
era(tmp,a[i]);
era(tmp,a[i]);
cur[a[i]]-=2;
dfs(tmp,a.size()/3,0,0);
cur[a[i]]+=2;
}
if(c[a[i]]<=3)
{
tmp=a;
era(tmp,a[i]);
cur[a[i]]--;
c[a[i]]++;
dfs(tmp,a.size()/3,0,1);
cur[a[i]]++;
c[a[i]]--;
}
}
// dfs(a,a.size()/3,0,1);
for(auto i:a)c[i]--,cur[i]--;
return ans;
}
int pile[155];
int tp=1;
int ID[312];
int ID2[312];
vector<int> a[4],b[4];
int now,turn=1;
char nam[555][13];
int card;
bool use;
void mo()
{
printf("%c IN %s\n",now+'A',nam[pile[tp]]);
a[now].pb(pile[tp++]);
sort(a[now].begin(),a[now].end());
}
void out(int x)
{
card=a[now][x];
use=0;
if(card==503)
printf("%c OUT %s %c\n",now+'A',nam[card],(now+turn+4)%4+'A');
else
printf("%c OUT %s\n",now+'A',nam[card]);
a[now].erase(a[now].begin()+x);
}
int nxt(int now)
{
return (now+turn+4)%4;
}
void ckzm()
{
if(cal(a[now])==0)
{
printf("%c SELFDRAWN\n%c WIN\n",now+'A',now+'A');
// system("pause");
exit(0);
}
}
void ckron(int x)
{
vector<int> tmp=a[x];
tmp.pb(card);
sort(tmp.begin(),tmp.end());
if(cal(tmp)==0)
{
printf("%c RON\n%c WIN\n",x+'A',x+'A');
// system("pause");
exit(0);
}
}
void pon(int x)
{
printf("%c PONG %s %s %s\n",x+'A',nam[card],nam[card],nam[card]);
era(a[x],card);
era(a[x],card);
now=x;
use=1;
ok=0;
}
void chow(int x,int ca,int cb,int cc)
{
printf("%c CHOW %s %s %s\n",x+'A',nam[ca],nam[cb],nam[cc]);
if(ca!=card)era(a[x],ca);
if(cb!=card)era(a[x],cb);
if(cc!=card)era(a[x],cc);
now=x;
use=1;
ok=0;
}
void ckpon(int x)
{
if(use)return ;
int cnt=0;
for(auto i:a[x])
if(i==card)cnt++;
if(cnt<=1)return ;
cnt=0;
vector<int> tmp;
for(auto i:a[x])
{
if(i==card)
{
if(cnt==2)tmp.pb(i);
else cnt++;
}
else tmp.pb(i);
}
if(cal(tmp)<cal(a[x]))pon(x);
return ;
}
int ch[555];
void ckchow(int x)
{
if(use||card>400)return ;
for(auto i:a[x])
ch[i]++;
vector<int> las=a[x];
int ori=cal(a[x]);
if(ch[card+1]&&ch[card+2])
{
vector<int> tmp=a[x];
era(tmp,card+1);
era(tmp,card+2);
if(cal(tmp)<ori)
chow(x,card,card+1,card+2);
}
if(!use&&ch[card-1]&&ch[card+1])
{
vector<int> tmp=a[x];
era(tmp,card-1);
era(tmp,card+1);
if(cal(tmp)<ori)
chow(x,card-1,card,card+1);
}
if(!use&&ch[card-2]&&ch[card-1])
{
vector<int> tmp=a[x];
era(tmp,card-2);
era(tmp,card-1);
if(cal(tmp)<ori)
chow(x,card-2,card-1,card);
}
for(auto i:las)
ch[i]--;
}
void dbg()
{
printf("now: %c\n",now+'A');
for(int i=0;i<=3;i++)
{
printf("card of %c: ",i+'A');
for(auto j:a[i])
printf("%s ",nam[j]);puts("");
// printf("xiangting: %d\n",cal(a[i]));
}
for(int i=1;i<=505;i++)
assert(c[i]==0&&cur[i]==0&&ch[i]==0);
}
int main()
{
ID['E']=401,ID['S']=402,ID['W']=403,ID['N']=404,ID['B']=405,ID['F']=406,ID['Z']=407;
ID2['M']=100,ID2['P']=200,ID2['S']=300;
nam[401][0]='E',nam[402][0]='S',nam[403][0]='W',nam[404][0]='N',nam[405][0]='B',nam[406][0]='F',nam[407][0]='Z';
for(int i=1;i<=3;i++)
for(int j=1;j<=9;j++)
nam[i*100+j][0]='0'+j,nam[i*100+j][1]=(i==1?'M':(i==2?'P':'S'));
strcpy(nam[503],"PASS");
strcpy(nam[502],"REVERSE");
strcpy(nam[501],"DOUBLE");
for(int i=1;i<=148;i++)
{
string s;
cin>>s;
if(s.size()>3)
{
if(s[0]=='P')pile[i]=503;
if(s[0]=='R')pile[i]=502;
if(s[0]=='D')pile[i]=501;
}
else if(s.size()==1)
{
pile[i]=ID[s[0]];
}
else pile[i]=ID2[s[1]]+s[0]-'0';
}
for(int i=1;i<=52;i++)
{
mo();
now=nxt(now);
}
for(int i=0;i<=3;i++)
sort(a[i].begin(),a[i].end());
while(tp<=148)
{
if(ok)mo();
// dbg();
if(a[now].back()>500)
{
out(a[now].size()-1);
if(card==503)now=(now+turn*2+4)%4;
if(card==502)turn*=-1,now=nxt(now);
ok=1;
continue;
}
ckzm();
int ori=cal(a[now]);
for(int i=a[now].size()-1;i>=0;i--)
{
vector<int> tmp=a[now];
tmp.erase(tmp.begin()+i);
// cout<<cal(tmp)<<" ";
if(cal(tmp)==ori)
{
out(i);
break;
}
}
for(int i=1,j=nxt(now);i<=3&&!use;i++,j=nxt(j))
ckron(j);
for(int i=1,j=nxt(now);i<=3&&!use;i++,j=nxt(j))
ckpon(j);
ckchow(nxt(now));
if(!use)now=nxt(now),ok=1;
}
puts("DRAW");
// system("pause");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 17ms
memory: 3660kb
input:
8M Z E 9P 3P 9S 5P W 3M 8P DOUBLE 5P Z 2P 3M 8S 2S 5P 5M E 6M 9S 6P 5S 7M 4S 3S 6M 3S 2M 9M 5S Z 7P 5P 8M 3M F 7M 2S N 4P 3S S PASS 1P 6S 3P 9P 9S 4M 8P N Z N 5M DOUBLE REVERSE S 3P 4M 4S 1S PASS 4P 6S 7S 7P 6S 9M REVERSE 3P 7P DOUBLE B 9P 4S 5S 7S 7S 7P 6S 9S B 9M S F 2P 1P PASS 9P DOUBLE 4P PASS 5...
output:
A IN 8M B IN Z C IN E D IN 9P A IN 3P B IN 9S C IN 5P D IN W A IN 3M B IN 8P C IN DOUBLE D IN 5P A IN Z B IN 2P C IN 3M D IN 8S A IN 2S B IN 5P C IN 5M D IN E A IN 6M B IN 9S C IN 6P D IN 5S A IN 7M B IN 4S C IN 3S D IN 6M A IN 3S B IN 2M C IN 9M D IN 5S A IN Z B IN 7P C IN 5P D IN 8M A IN 3M B IN F...
result:
ok 84 lines
Test #2:
score: -100
Wrong Answer
time: 76ms
memory: 3712kb
input:
REVERSE 4S 8S 6P 4P F 1P W 9P N 9M B 7S 5P PASS 5M 7M 9S 1S 2P 3S 6S B 2S 9P 9M 4S 3M W 6P 8P W 2M 7P 6M 8M 2S S F W DOUBLE E 2P E 2M 8S 2S 9P 1M 7S 8M N 4P 1S 1P S 3P 3S B 3M 7P 5S 3M 5M 7M 2S E 9P 1M 7P 3P 5P REVERSE 5S 9S 8M 4M 7P 1S 7M 1M 1M 8P 9S 6M 7S PASS 4M 3M 9M B 2P 4P 6S F 4S 6P 6P 7M 1S ...
output:
A IN REVERSE B IN 4S C IN 8S D IN 6P A IN 4P B IN F C IN 1P D IN W A IN 9P B IN N C IN 9M D IN B A IN 7S B IN 5P C IN PASS D IN 5M A IN 7M B IN 9S C IN 1S D IN 2P A IN 3S B IN 6S C IN B D IN 2S A IN 9P B IN 9M C IN 4S D IN 3M A IN W B IN 6P C IN 8P D IN W A IN 2M B IN 7P C IN 6M D IN 8M A IN 2S B IN...
result:
wrong answer 114th lines differ - expected: 'A OUT 4P', found: 'A OUT 3P'