QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269890#5821. 交换机shown0 26ms9232kbC++142.1kb2023-11-30 10:43:082023-11-30 10:43:10

Judging History

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

  • [2023-11-30 10:43:10]
  • 评测
  • 测评结果:0
  • 用时:26ms
  • 内存:9232kb
  • [2023-11-30 10:43:08]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int nn=100005;
const int kk=1440;
const int mod=999979;

int n,k;
struct node{
	int num;
	//char id[18];
	int time;
}a[nn];
int ans,now;

int b[nn],c[nn];
//int team[nn],head,tail;
queue<int> q;

int Hash(char id[])
{
	int res=0;
	for(int i=0;i<strlen(id);i++)
	{
		res*=mod;res+=id[i];
	}
	res%=mod;
	if(res<0) res+=mod;
	res++;
	return res;
}

int frst[mod+3],nxt[nn],tot;
char go[nn][18];
int Make(int h,char id[],int time)
{
	//printf("make-OK0 time=%d h=%d\n",time,h);    //
	for(int i=frst[h];i;i=nxt[i])
	{
		char v[18];
		for(int j=0;j<18;j++) v[j]=go[i][j];
		
		int jie=0;
		for(int j=0;j<18;j++)
		{
			if(v[j]!=id[j])
			{
				jie=1;
				break;
			}
		}
		if(jie==0)
		{
			//printf("make-f1-if return\n");       //
			return i;
		}
	}
	//printf("make-OK1\n");                        //
	
	tot++;nxt[tot]=frst[h];frst[h]=tot;//go[tot]=id;
	for(int j=0;j<18;j++) go[tot][j]=id[j];
	return tot;
}

bool cmpn(node,node);

int main()
{
	//freopen("switch.in","r",stdin);
	//freopen("switch.out","w",stdout);
	
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		//printf("m-f1-OK0 i=%d\n",i);             //
		char id[18];
		int hour,minute;
		scanf("%s",id);
		//printf("m-f1-OK1 read_id\n");            //
		scanf("%d:%d",&hour,&minute);
		a[i].time=hour*60+minute;
		//printf("m-f1-OK2\n");                    //
		
		int x=Hash(id);
		//printf("m-f1-OK3\n");                    //
		
		a[i].num=Make(x,id,a[i].time);
	}
	
	sort(a,a+n,cmpn);
	
	q.push(a[0].num);
	b[a[0].num]=1;
	now=1;
	for(int head=0,tail=0;head<=tail;head++)
	{
		for(;tail+1<n;tail++)
		{
			if(a[tail+1].num<a[head].num+k)
			{
				tail++;
				c[a[tail].num]=a[tail].time;
				if(b[a[tail].num]==0)
				{
					b[a[tail].num]=1;
					now++;
				}
			}
		}
		ans=max(now,ans);
		if(c[a[head].num]==a[head].time)
		{
			b[a[head].num]=0;
		}
	}
	
	printf("%d",ans);
	
	return 0;
}
bool cmpn(node x,node y)
{
	if(x.time!=y.time) return x.time<y.time;
	return x.num<y.num;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6040kb

input:

114 34
276BF170F8DFBBDD 18:48
FF98EB813GF76CCF 12:10
E770B692178820GG 18:44
1C23B74556009EFE 07:46
A772376BF9B3AGGD 02:19
8CG985327G2D8DGG 16:17
D5C5846GBD734718 22:54
06897862D1A8849B 11:24
3AF5A953601D3949 12:11
9G4BGEB06390C136 07:46
043GE167G9187004 12:32
8E7D32FCF9AFE2A1 01:08
276BF170F8DFBBDD ...

output:

30

result:

wrong answer 1st lines differ - expected: '7', found: '30'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 4512kb

input:

405 34
45FAE883E13G3F2F 15:32
26B5D8B0536AFA93 00:33
0DFCDG4CACF0EF5E 19:42
E05BA7777G48A477 13:19
D30DE2EB4GF58397 22:44
36C38G75DE4A636G 04:03
1609C891FGC9A8FB 01:53
G0274467BCD95131 07:25
C52A230FD0A008A9 11:26
969BB8BA05E2F4GD 15:43
1844848A464D130F 03:09
D30DE2EB4GF58397 06:47
717B775CG4D6EC4G ...

output:

96

result:

wrong answer 1st lines differ - expected: '20', found: '96'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 5880kb

input:

75 6
27E2EG2748DD8928 02:30
61ED38B66941E937 04:37
E61EFGBF3DCF0784 05:18
8F70C8GG15E3E2AE 09:52
27E2EG2748DD8928 10:30
27E2EG2748DD8928 04:14
D4D006G6D23A0ABF 22:29
B9G429BDC8D40141 11:51
5AC60CBA532C669A 10:09
E10EDDE80G2206DE 10:40
9896GD4ADAC45CF1 01:07
D20G39D6F5G8595B 22:52
B9G429BDC8D40141 12...

output:

14

result:

wrong answer 1st lines differ - expected: '3', found: '14'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 5868kb

input:

20 32
1F7E8GBBGF0AFA4A 22:23
1B2953319455F0C3 19:03
97E149BECD52DBB1 10:45
6482AEAAF1GF35GA 06:56
985009C28BD4F256 12:36
1F7E8GBBGF0AFA4A 18:17
985009C28BD4F256 15:56
985009C28BD4F256 12:10
985009C28BD4F256 03:12
985009C28BD4F256 07:58
985009C28BD4F256 11:26
1B2953319455F0C3 07:48
1F7E8GBBGF0AFA4A 0...

output:

5

result:

wrong answer 1st lines differ - expected: '3', found: '5'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 4104kb

input:

309 5
AD45366EBGB28A33 12:47
C21471A6BCCA20AE 00:24
8G55FE68A3EFEADA 07:58
A5DGCC857266BA43 23:46
9D585GA710B8B290 20:14
AF1EBFG5D27GF81A 13:26
716B381224GD9BEF 08:48
6798CE358C739DC1 11:46
4CC063C7CC73856C 13:50
F091759E477GCE64 05:09
9E1B0A624B0F401F 10:17
C6488E63E2EC59FD 18:05
C4C207035AFC370D 2...

output:

47

result:

wrong answer 1st lines differ - expected: '6', found: '47'

Test #6:

score: 0
Wrong Answer
time: 11ms
memory: 8448kb

input:

30416 99
3BB8235CE2F92G12 02:26
CG6D3B8D1113B306 20:55
F4D01C26GC2GDD3B 08:49
B28978G6BE1268A0 03:52
935A7831GG4487C4 23:05
6C6FGA91B5AG9248 00:48
D82G2F925G5679E7 18:44
4B9673F64E705295 01:37
B8B7C4C4GDC697G7 09:33
C4B7C57G10GCAG09 07:47
8C3D83237713CF0C 16:00
561BDA5C7989C53A 09:50
C8B286B0CAC2BBC...

output:

201

result:

wrong answer 1st lines differ - expected: '2049', found: '201'

Test #7:

score: 0
Wrong Answer
time: 23ms
memory: 9232kb

input:

81690 40
1A74CDFA14362FC6 18:54
GCF498A6F9F14DF8 12:18
7C79717C3DE81BBB 10:52
1CE425GFF664G2A3 22:58
1AB76683D2FCF2F7 03:46
0225D154E01CC0B5 17:30
F8CA1E8546GA585D 02:01
D003FC6B4144D30E 21:01
E9C6ED88B819345D 10:30
38FA37859D424185 14:33
FC52FGG1780CG6EC 17:33
56G87919461CFE56 06:29
5D5F0BEC9G0D5E9...

output:

508

result:

wrong answer 1st lines differ - expected: '2281', found: '508'

Test #8:

score: 0
Wrong Answer
time: 20ms
memory: 8696kb

input:

58105 75
BCG8G3C03EG6GD79 11:54
8G6FF017858152FG 07:40
F0D52856G4418FAF 10:10
30DAG5FCD5506279 06:46
8C02A64BD367DG04 02:24
2D7EAG9E72GC60EG 13:16
EBD3536C5C80084G 20:31
4C72C80FA6B8D2G9 01:24
G520EA7GD917EFDA 05:25
0E78C6EG7B2D29G2 08:18
CC121032C111F91A 22:45
G038616FC67DF881 20:03
76052AC8D6E5G0E...

output:

156

result:

wrong answer 1st lines differ - expected: '2918', found: '156'

Test #9:

score: 0
Wrong Answer
time: 26ms
memory: 9100kb

input:

89547 76
1C29478E28A4F507 23:19
3F6F29156C0C4214 04:02
B5CBF7BG0053DGF2 20:59
C64D0DG2F331FBE5 11:38
81C781E6B404EB8F 01:39
12EDCCB4DGFDB9B8 02:44
CE9137G7ECGAFA6B 11:32
49BE6GG7A401DC9D 06:55
42C1AAFG0C365GB5 22:09
GD1FA9DBG2CDCE06 14:43
54D4F3AEGGF1AAAE 06:40
DE2712BC5DAA5D5G 15:44
BB4BE69149636EA...

output:

145

result:

wrong answer 1st lines differ - expected: '4487', found: '145'

Test #10:

score: 0
Wrong Answer
time: 1ms
memory: 4896kb

input:

967 95
31G60BG2G76BAF0A 19:40
687406G513579F15 19:12
28GBA5G380GC46B7 11:57
6550C58AG239827G 08:29
090DC08AA7C94C65 01:09
45F948FDB87897B2 11:30
5465AECA0GE80CF4 17:38
B88BEC3A6G8CA6C3 19:52
E7GECA1GAF553E4F 21:33
4C3GA5A7A7303F7A 19:56
G3G72CAC22912151 11:55
G5CA072AF0068916 10:32
11284420FGED50D6 ...

output:

142

result:

wrong answer 1st lines differ - expected: '78', found: '142'