QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#73722	#4208. Flight to the Ford	huzhaoyang	100 ✓	195ms	3780kb	C++14	2.0kb	2023-01-27 19:19:11	2023-02-03 22:49:55

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-02-03 22:49:55]
评测

测评结果：100
用时：195ms
内存：3780kb

查看

[2023-01-27 19:19:11]
提交

answer

#include<bits/stdc++.h>
#include "communication.h"
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int N=50;
int s,t,f[N][N],fI[N][N],fJ[N][N];
struct Node{
	int sz;
	vector<pii>v;
	Node(){
		sz=0,v.clear();
	}
	Node(int n){
		sz=n;
		v=vector<pii>{make_pair(1,n)};
	}
}S,T,S1,S2,T1,T2;
Node merge(Node x,Node y){
	Node k;
	k.sz=x.sz+y.sz;
	for(pii i:x.v)k.v.push_back(i);
	for(pii i:y.v)k.v.push_back(i);
	return k;
}
void divide(Node k,int s,Node &x,Node &y){
	x=Node(),y=Node();
	x.sz=s,y.sz=k.sz-s;
	for(pii i:k.v){
		int l=i.se-i.fi+1;
		if (!s)y.v.push_back(i);
		else{
			if (s>=l)x.v.push_back(i),s-=l;
			else{
				x.v.push_back(make_pair(i.fi,i.fi+s-1));
				y.v.push_back(make_pair(i.fi+s,i.se));
				s=0;
			}
		}
	}
}
void init(){
	memset(f,0x3f,sizeof(f));
	for(int s=0;s<N;s++)
		for(int i=0;i<=s;i++){
			int j=s-i;
			if (s<3){f[i][j]=0;continue;}
			for(int I=0;I<=i;I++)
				for(int J=0;J<=j;J++){
					if (f[i][j]>max(f[I+J][i-I],f[i+j-I-J][I])+1){
						fI[i][j]=I,fJ[i][j]=J;
						f[i][j]=max(f[I+J][i-I],f[i+j-I-J][I])+1;
					}
				}
		}
}
void encode(int n,int x){
	init(),S=Node(n),T=Node();
	while (S.sz+T.sz>2){
		if (S.sz+T.sz<N)s=fI[S.sz][T.sz],t=fJ[S.sz][T.sz];
		else s=(S.sz+1>>1),t=(T.sz>>1);
		divide(S,s,S1,S2),divide(T,t,T1,T2);
		bool flag=0;
		for(pii i:S1.v)
			if ((i.fi<=x)&&(x<=i.se))flag=1;
		for(pii i:T1.v)
			if ((i.fi<=x)&&(x<=i.se))flag=1;
		if (send(flag))S=merge(S1,T1),T=S2;
		else S=merge(S2,T2),T=S1;
	}
}
pair<int,int> decode(int n){
	init(),S=Node(n),T=Node();
	while (S.sz+T.sz>2){
		if (S.sz+T.sz<N)s=fI[S.sz][T.sz],t=fJ[S.sz][T.sz];
		else s=(S.sz+1>>1),t=(T.sz>>1);
		divide(S,s,S1,S2),divide(T,t,T1,T2);
		if (receive())S=merge(S1,T1),T=S2;
		else S=merge(S2,T2),T=S1;
	}
	int x=0,y=0;
	for(pii i:S.v)
		for(int j=i.fi;j<=i.se;j++){
			if (!x)x=j;
			else y=j;
		}
	for(pii i:T.v)
		for(int j=i.fi;j<=i.se;j++){
			if (!x)x=j;
			else y=j;
		}
	if (!y)y=x;
	return make_pair(x,y);
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 11ms

memory: 3736kb

Overall Time Limit: 500ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #2:

score: 15

Accepted

time: 7ms

memory: 3616kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #3:

score: 15

Accepted

time: 9ms

memory: 3684kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Test #4:

score: 15

Accepted

time: 12ms

memory: 3744kb

Overall Time Limit: 500ms

input:

output:

input:

output:

result:

points 1.0

Test #5:

score: 15

Accepted

time: 38ms

memory: 3720kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #6:

score: 15

Accepted

time: 4ms

memory: 3752kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #7:

score: 15

Accepted

time: 11ms

memory: 3636kb

Overall Time Limit: 375ms

input:

output:

input:

output:

result:

points 1.0

Subtask #2:

score: 85

Accepted

Test #8:

score: 85

Accepted

time: 101ms

memory: 3708kb

Overall Time Limit: 2210ms

input:

output:

input:

output:

result:

points 1.0

Test #9:

score: 85

Accepted

time: 134ms

memory: 3652kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #10:

score: 85

Accepted

time: 134ms

memory: 3776kb

Overall Time Limit: 2020ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #11:

score: 85

Accepted

time: 69ms

memory: 3644kb

Overall Time Limit: 1235ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #12:

score: 85

Accepted

time: 111ms

memory: 3776kb

Overall Time Limit: 2500ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #13:

score: 85

Accepted

time: 133ms

memory: 3780kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #14:

score: 85

Accepted

time: 148ms

memory: 3648kb

Overall Time Limit: 2955ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #15:

score: 85

Accepted

time: 141ms

memory: 3752kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #16:

score: 85

Accepted

time: 86ms

memory: 3712kb

Overall Time Limit: 1210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #17:

score: 85

Accepted

time: 38ms

memory: 3752kb

Overall Time Limit: 1050ms

input:

output:

input:

output:

result:

points 1.0

Test #18:

score: 85

Accepted

time: 83ms

memory: 3652kb

Overall Time Limit: 2300ms

input:

output:

input:

output:

result:

points 1.0

Test #19:

score: 85

Accepted

time: 72ms

memory: 3712kb

Overall Time Limit: 1255ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #20:

score: 85

Accepted

time: 71ms

memory: 3776kb

Overall Time Limit: 1250ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #21:

score: 85

Accepted

time: 10ms

memory: 3692kb

Overall Time Limit: 250ms

input:

output:

input:

output:

result:

points 1.0

Test #22:

score: 85

Accepted

time: 79ms

memory: 3692kb

Overall Time Limit: 1230ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #23:

score: 85

Accepted

time: 134ms

memory: 3780kb

Overall Time Limit: 3210ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #24:

score: 85

Accepted

time: 76ms

memory: 3688kb

Overall Time Limit: 1300ms

input:

output:

input:

output:

result:

points 1.0

Test #25:

score: 85

Accepted

time: 195ms

memory: 3712kb

Overall Time Limit: 4995ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #26:

score: 85

Accepted

time: 135ms

memory: 3632kb

Overall Time Limit: 2000ms

input:

output:

input:

output:

result:

points 1.0

Test #27:

score: 85

Accepted

time: 77ms

memory: 3704kb

Overall Time Limit: 1220ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #28:

score: 85

Accepted

time: 104ms

memory: 3648kb

Overall Time Limit: 1710ms

input:

output:

input:

output:

result:

points 1.0

Test #29:

score: 85

Accepted

time: 115ms

memory: 3712kb

Overall Time Limit: 2355ms

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #30:

score: 85

Accepted

time: 137ms

memory: 3748kb

Overall Time Limit: 2960ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0

Test #31:

score: 85

Accepted

time: 133ms

memory: 3660kb

Overall Time Limit: 2965ms

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

input:

output:

result:

points 1.0