QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#831203 | #8952. 解谜游戏 | 275307894a# | 86.373333 | 68ms | 8144kb | C++14 | 3.3kb | 2024-12-25 11:43:18 | 2024-12-25 11:43:27 |
Judging History
answer
#include<bits/stdc++.h>
#include "puzzle.h"
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e3+5,M=(1<<28)+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int nn,pp[N],qcnt;
vector<int> p,vis,rgt;
int n;
void divide(vector<int> st,int sum,int w){
if(!sum) return;
if(st.size()==1){
vis[st[0]]=1;rgt.push_back(st[0]);
return;
}
int m=st.size()/2;
vector<int> s1(st.begin(),st.begin()+m),s2(st.begin()+m,st.end());
for(int i=0;i<s1.size();i++) swap(p[s1[i]],p[rgt[i]]);
int pw=w-query(p)-s1.size();
// gdb(pw);
for(int i=0;i<s1.size();i++) swap(p[s1[i]],p[rgt[i]]);
divide(s1,pw,w);divide(s2,sum-pw,w);
}
int alp[N][N];
void play(int nn){
mt19937 rnd(28382);
n=nn;p.resize(n);vis.resize(n);
iota(all(p),0);
if(n==1) return check(p);
shuffle(all(p),rnd);
while(query(p)){
shuffle(all(p),rnd);
}
for(int i=0;i<n;i++) alp[p[i]][i]=1;
int cnt=0;
vector<int> id(n-1);
iota(all(id),1);shuffle(all(id),rnd);
for(int i:id){
swap(p[0],p[i]);
int w=query(p);
if(w){
if(w==2){
cnt=w;vis[i]=vis[0]=1;
break;
}
int w1=p[0],w2=p[i];
while(1){
auto q=p;
shuffle(q.begin()+1,q.end(),rnd);
if(!query(q)){vis[i]=1;break;}
q=p;
swap(q[0],q[i]);
shuffle(q.begin()+1,q.end(),rnd);
swap(q[0],q[i]);
if(!query(q)){vis[0]=1;break;}
}
cnt=1;break;
break;
}
swap(p[0],p[i]);
}
for(int i=0;i<n;i++) if(vis[i]) rgt.push_back(i);
while(cnt^n){
int w=cnt;
gdb(w,p[0],p[1],p[2],p[3],p[4],rgt[0],vis[2]);
while(w==cnt){
for(int i=0;i<n;i++) if(!vis[i]) alp[p[i]][i]=1;
static int ap[N];Me(ap,0);
for(int i:rgt) ap[p[i]]=1;
for(int i=0;i<n;i++) if(!vis[i]){
int x=R(n)-1;
while(ap[x]) x=R(n)-1;
p[i]=x;ap[x]=1;
}
int flag=0;
for(int i=0;i<n;i++) if(!vis[i]&&!alp[p[i]][i]) flag=1;
if(!flag) continue;
w=query(p);
// gdb(w,p[0],p[1],p[2],p[3],p[4]);
}
// gdb(w,p[0],p[1],p[2]);
vector<int> st;
vector<int> id(n+1);
iota(all(id),0);shuffle(id.begin(),id.begin()+n,rnd);
for(int i:id)if(rgt.size()<w){
if(i<n&&!vis[i]&&!alp[p[i]][i]) st.push_back(i);
if(i==n||st.size()==cnt){
for(int i=0;i<st.size();i++) swap(p[st[i]],p[rgt[i]]);
int pw=query(p);
for(int i=0;i<st.size();i++) swap(p[st[i]],p[rgt[i]]);
if(pw<w-st.size()){
divide(st,w-pw-st.size(),w);
}
st.clear();
}
}
cnt=w;
}
check(p);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 2
Accepted
Test #1:
score: 2
Accepted
time: 0ms
memory: 3820kb
input:
1 2 816815200
result:
ok accepted: cnt = 2
Test #2:
score: 2
Accepted
time: 0ms
memory: 3820kb
input:
1 3 723182155
result:
ok accepted: cnt = 22
Test #3:
score: 2
Accepted
time: 0ms
memory: 3840kb
input:
1 5 971867682
result:
ok accepted: cnt = 10
Test #4:
score: 2
Accepted
time: 0ms
memory: 3804kb
input:
1 3 887042235
result:
ok accepted: cnt = 7
Test #5:
score: 2
Accepted
time: 0ms
memory: 3836kb
input:
1 3 568659743
result:
ok accepted: cnt = 22
Test #6:
score: 2
Accepted
time: 0ms
memory: 4032kb
input:
1 5 930991667
result:
ok accepted: cnt = 18
Test #7:
score: 2
Accepted
time: 0ms
memory: 3900kb
input:
1 5 185481439
result:
ok accepted: cnt = 14
Test #8:
score: 2
Accepted
time: 0ms
memory: 3900kb
input:
1 5 405685705
result:
ok accepted: cnt = 11
Test #9:
score: 2
Accepted
time: 0ms
memory: 3916kb
input:
1 5 693401039
result:
ok accepted: cnt = 13
Test #10:
score: 2
Accepted
time: 1ms
memory: 3840kb
input:
1 5 570594473
result:
ok accepted: cnt = 13
Subtask #2:
score: 4
Accepted
Test #11:
score: 4
Accepted
time: 0ms
memory: 4016kb
input:
2 2 931107645
result:
ok accepted: cnt = 2
Test #12:
score: 4
Accepted
time: 0ms
memory: 4032kb
input:
2 4 512124670
result:
ok accepted: cnt = 10
Test #13:
score: 4
Accepted
time: 0ms
memory: 4032kb
input:
2 4 793864173
result:
ok accepted: cnt = 16
Test #14:
score: 4
Accepted
time: 0ms
memory: 3788kb
input:
2 7 322910591
result:
ok accepted: cnt = 17
Test #15:
score: 4
Accepted
time: 0ms
memory: 3912kb
input:
2 9 316192686
result:
ok accepted: cnt = 33
Test #16:
score: 4
Accepted
time: 0ms
memory: 3800kb
input:
2 10 350886420
result:
ok accepted: cnt = 21
Test #17:
score: 4
Accepted
time: 0ms
memory: 3896kb
input:
2 10 914937911
result:
ok accepted: cnt = 43
Test #18:
score: 4
Accepted
time: 0ms
memory: 4152kb
input:
2 10 68729974
result:
ok accepted: cnt = 33
Test #19:
score: 4
Accepted
time: 0ms
memory: 3828kb
input:
2 10 15788440
result:
ok accepted: cnt = 29
Test #20:
score: 4
Accepted
time: 0ms
memory: 3856kb
input:
2 10 950846282
result:
ok accepted: cnt = 31
Subtask #3:
score: 6
Accepted
Test #21:
score: 6
Accepted
time: 0ms
memory: 3820kb
input:
3 2 667362636
result:
ok accepted: cnt = 4
Test #22:
score: 6
Accepted
time: 0ms
memory: 3776kb
input:
3 4 890842001
result:
ok accepted: cnt = 10
Test #23:
score: 6
Accepted
time: 0ms
memory: 4120kb
input:
3 3 225277415
result:
ok accepted: cnt = 11
Test #24:
score: 6
Accepted
time: 1ms
memory: 3916kb
input:
3 26 235413642
result:
ok accepted: cnt = 100
Test #25:
score: 6
Accepted
time: 1ms
memory: 3920kb
input:
3 25 139642984
result:
ok accepted: cnt = 107
Test #26:
score: 6
Accepted
time: 1ms
memory: 3968kb
input:
3 30 991911708
result:
ok accepted: cnt = 163
Test #27:
score: 6
Accepted
time: 0ms
memory: 4000kb
input:
3 30 4514256
result:
ok accepted: cnt = 131
Test #28:
score: 6
Accepted
time: 1ms
memory: 5948kb
input:
3 30 157113423
result:
ok accepted: cnt = 155
Test #29:
score: 6
Accepted
time: 1ms
memory: 3948kb
input:
3 30 557648974
result:
ok accepted: cnt = 142
Test #30:
score: 6
Accepted
time: 1ms
memory: 4132kb
input:
3 30 645022468
result:
ok accepted: cnt = 152
Test #31:
score: 6
Accepted
time: 0ms
memory: 3824kb
input:
4 2 427653480
result:
ok accepted: cnt = 4
Test #32:
score: 6
Accepted
time: 0ms
memory: 3836kb
input:
4 3 219860551
result:
ok accepted: cnt = 22
Test #33:
score: 6
Accepted
time: 0ms
memory: 3808kb
input:
4 4 165138325
result:
ok accepted: cnt = 8
Test #34:
score: 6
Accepted
time: 1ms
memory: 4380kb
input:
4 93 525060479
result:
ok accepted: cnt = 616
Test #35:
score: 6
Accepted
time: 1ms
memory: 6256kb
input:
4 99 829735778
result:
ok accepted: cnt = 714
Subtask #4:
score: 8
Accepted
Test #36:
score: 8
Accepted
time: 1ms
memory: 4208kb
input:
4 100 6610818
result:
ok accepted: cnt = 586
Test #37:
score: 8
Accepted
time: 1ms
memory: 4212kb
input:
4 100 653323659
result:
ok accepted: cnt = 711
Test #38:
score: 8
Accepted
time: 1ms
memory: 4252kb
input:
4 100 268513130
result:
ok accepted: cnt = 690
Test #39:
score: 8
Accepted
time: 1ms
memory: 4136kb
input:
4 100 479581529
result:
ok accepted: cnt = 619
Test #40:
score: 8
Accepted
time: 0ms
memory: 6080kb
input:
4 100 119844914
result:
ok accepted: cnt = 606
Subtask #5:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 0ms
memory: 3824kb
input:
5 2 527801655
result:
ok accepted: cnt = 2
Test #42:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
5 5 235665947
result:
ok accepted: cnt = 14
Test #43:
score: 10
Accepted
time: 0ms
memory: 3892kb
input:
5 3 648413779
result:
ok accepted: cnt = 11
Test #44:
score: 10
Accepted
time: 5ms
memory: 5188kb
input:
5 272 737778828
result:
ok accepted: cnt = 2152
Test #45:
score: 10
Accepted
time: 3ms
memory: 6796kb
input:
5 278 173436130
result:
ok accepted: cnt = 1944
Test #46:
score: 10
Accepted
time: 6ms
memory: 6836kb
input:
5 300 997862299
result:
ok accepted: cnt = 2346
Test #47:
score: 10
Accepted
time: 6ms
memory: 5304kb
input:
5 300 764271855
result:
ok accepted: cnt = 2173
Test #48:
score: 10
Accepted
time: 6ms
memory: 6824kb
input:
5 300 428892383
result:
ok accepted: cnt = 2432
Test #49:
score: 10
Accepted
time: 6ms
memory: 5308kb
input:
5 300 166706392
result:
ok accepted: cnt = 2586
Test #50:
score: 10
Accepted
time: 6ms
memory: 6764kb
input:
5 300 843444435
result:
ok accepted: cnt = 2297
Subtask #6:
score: 10
Accepted
Test #51:
score: 10
Accepted
time: 0ms
memory: 3856kb
input:
6 2 183795068
result:
ok accepted: cnt = 2
Test #52:
score: 10
Accepted
time: 0ms
memory: 3840kb
input:
6 5 63668012
result:
ok accepted: cnt = 17
Test #53:
score: 10
Accepted
time: 0ms
memory: 3904kb
input:
6 5 990398365
result:
ok accepted: cnt = 15
Test #54:
score: 10
Accepted
time: 14ms
memory: 7380kb
input:
6 488 942578687
result:
ok accepted: cnt = 4252
Test #55:
score: 10
Accepted
time: 14ms
memory: 6504kb
input:
6 475 915148470
result:
ok accepted: cnt = 4368
Test #56:
score: 10
Accepted
time: 11ms
memory: 6212kb
input:
6 500 736505651
result:
ok accepted: cnt = 4210
Test #57:
score: 10
Accepted
time: 15ms
memory: 6324kb
input:
6 500 352417213
result:
ok accepted: cnt = 4077
Test #58:
score: 10
Accepted
time: 13ms
memory: 7680kb
input:
6 500 80534667
result:
ok accepted: cnt = 4313
Test #59:
score: 10
Accepted
time: 11ms
memory: 5932kb
input:
6 500 811975157
result:
ok accepted: cnt = 4115
Test #60:
score: 10
Accepted
time: 15ms
memory: 7136kb
input:
6 500 471392863
result:
ok accepted: cnt = 4174
Subtask #7:
score: 46.3733
Acceptable Answer
Test #61:
score: 60
Accepted
time: 0ms
memory: 3832kb
input:
7 2 412859550
result:
ok accepted: cnt = 2
Test #62:
score: 60
Accepted
time: 0ms
memory: 3832kb
input:
7 4 892225546
result:
ok accepted: cnt = 10
Test #63:
score: 60
Accepted
time: 0ms
memory: 3820kb
input:
7 4 577686541
result:
ok accepted: cnt = 12
Test #64:
score: 60
Accepted
time: 47ms
memory: 7524kb
input:
7 902 974849567
result:
ok accepted: cnt = 8587
Test #65:
score: 60
Accepted
time: 52ms
memory: 7676kb
input:
7 939 155203710
result:
ok accepted: cnt = 8640
Test #66:
score: 47.43
Acceptable Answer
time: 60ms
memory: 8048kb
input:
7 1000 253107507
result:
points 0.7905 partially_correct: cnt = 10271
Test #67:
score: 47.23
Acceptable Answer
time: 65ms
memory: 7860kb
input:
7 1000 882029420
result:
points 0.7871666667 partially_correct: cnt = 10331
Test #68:
score: 48.3833
Acceptable Answer
time: 64ms
memory: 7844kb
input:
7 1000 199421982
result:
points 0.8063888889 partially_correct: cnt = 9985
Test #69:
score: 49.23
Acceptable Answer
time: 59ms
memory: 7852kb
input:
7 1000 749220884
result:
points 0.8205 partially_correct: cnt = 9731
Test #70:
score: 48.5833
Acceptable Answer
time: 64ms
memory: 7848kb
input:
7 1000 729055050
result:
points 0.8097222222 partially_correct: cnt = 9925
Test #71:
score: 60
Accepted
time: 0ms
memory: 3824kb
input:
7 2 375338281
result:
ok accepted: cnt = 4
Test #72:
score: 60
Accepted
time: 0ms
memory: 3872kb
input:
7 5 914443594
result:
ok accepted: cnt = 21
Test #73:
score: 60
Accepted
time: 0ms
memory: 3840kb
input:
7 5 310479620
result:
ok accepted: cnt = 15
Test #74:
score: 48.9933
Acceptable Answer
time: 63ms
memory: 7976kb
input:
7 982 660842623
result:
points 0.8165555556 partially_correct: cnt = 9802
Test #75:
score: 48.4
Acceptable Answer
time: 63ms
memory: 7984kb
input:
7 985 92435101
result:
points 0.8066666667 partially_correct: cnt = 9980
Test #76:
score: 46.8633
Acceptable Answer
time: 68ms
memory: 7788kb
input:
7 1000 901527471
result:
points 0.7810555556 partially_correct: cnt = 10441
Test #77:
score: 46.47
Acceptable Answer
time: 66ms
memory: 7856kb
input:
7 1000 891945482
result:
points 0.7745 partially_correct: cnt = 10559
Test #78:
score: 48.0433
Acceptable Answer
time: 64ms
memory: 7844kb
input:
7 1000 461988571
result:
points 0.8007222222 partially_correct: cnt = 10087
Test #79:
score: 47.77
Acceptable Answer
time: 63ms
memory: 7888kb
input:
7 1000 588921486
result:
points 0.7961666667 partially_correct: cnt = 10169
Test #80:
score: 60
Accepted
time: 60ms
memory: 7856kb
input:
7 1000 819181186
result:
ok accepted: cnt = 9201
Test #81:
score: 60
Accepted
time: 0ms
memory: 3824kb
input:
7 2 509390821
result:
ok accepted: cnt = 2
Test #82:
score: 60
Accepted
time: 0ms
memory: 4116kb
input:
7 3 932973010
result:
ok accepted: cnt = 8
Test #83:
score: 60
Accepted
time: 0ms
memory: 3868kb
input:
7 3 704198002
result:
ok accepted: cnt = 6
Test #84:
score: 48.4767
Acceptable Answer
time: 58ms
memory: 7832kb
input:
7 996 844688748
result:
points 0.8079444444 partially_correct: cnt = 9957
Test #85:
score: 60
Accepted
time: 55ms
memory: 7648kb
input:
7 935 983758765
result:
ok accepted: cnt = 9319
Test #86:
score: 47.6533
Acceptable Answer
time: 60ms
memory: 7912kb
input:
7 1000 560957955
result:
points 0.7942222222 partially_correct: cnt = 10204
Test #87:
score: 48.4633
Acceptable Answer
time: 62ms
memory: 7848kb
input:
7 1000 381616996
result:
points 0.8077222222 partially_correct: cnt = 9961
Test #88:
score: 48.9767
Acceptable Answer
time: 65ms
memory: 7844kb
input:
7 1000 607168013
result:
points 0.8162777778 partially_correct: cnt = 9807
Test #89:
score: 47.38
Acceptable Answer
time: 59ms
memory: 8144kb
input:
7 1000 755432541
result:
points 0.7896666667 partially_correct: cnt = 10286
Test #90:
score: 48.82
Acceptable Answer
time: 63ms
memory: 8144kb
input:
7 1000 675700852
result:
points 0.8136666667 partially_correct: cnt = 9854
Test #91:
score: 60
Accepted
time: 0ms
memory: 3816kb
input:
7 2 91873452
result:
ok accepted: cnt = 2
Test #92:
score: 60
Accepted
time: 0ms
memory: 3868kb
input:
7 4 336570576
result:
ok accepted: cnt = 17
Test #93:
score: 60
Accepted
time: 0ms
memory: 4116kb
input:
7 4 617201184
result:
ok accepted: cnt = 7
Test #94:
score: 60
Accepted
time: 51ms
memory: 7652kb
input:
7 904 396880646
result:
ok accepted: cnt = 8153
Test #95:
score: 60
Accepted
time: 52ms
memory: 7712kb
input:
7 906 970970547
result:
ok accepted: cnt = 8522
Test #96:
score: 48.5633
Acceptable Answer
time: 66ms
memory: 7844kb
input:
7 1000 960558936
result:
points 0.8093888889 partially_correct: cnt = 9931
Test #97:
score: 46.7067
Acceptable Answer
time: 58ms
memory: 7932kb
input:
7 1000 238446836
result:
points 0.7784444444 partially_correct: cnt = 10488
Test #98:
score: 48.3733
Acceptable Answer
time: 65ms
memory: 7792kb
input:
7 1000 897094536
result:
points 0.8062222222 partially_correct: cnt = 9988
Test #99:
score: 46.3733
Acceptable Answer
time: 63ms
memory: 7848kb
input:
7 1000 820891454
result:
points 0.7728888889 partially_correct: cnt = 10588
Test #100:
score: 49.2533
Acceptable Answer
time: 65ms
memory: 7852kb
input:
7 1000 586475353
result:
points 0.8208888889 partially_correct: cnt = 9724