QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#282243#1173. Knowledge Is...HanghangWA 2ms9588kbC++14728b2023-12-11 16:43:452023-12-11 16:43:46

Judging History

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

  • [2023-12-11 16:43:46]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：9588kb
查看
  • [2023-12-11 16:43:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+3;
int n,m,ans[N];
bool v[N];
struct Nod{int l,r,id;}a[N],b[N];
bool CL(Nod a,Nod b){return a.l<b.l;}
bool CR(Nod a,Nod b){return a.r<b.r;}
bool Chk(int x)
{
	for(int i=1;i<=x;i++)if(a[i].r>=b[n-x+i].l)return 0;
	return 1;
}
int main()
{
	cin>>n>>m;int l=0,r=n/2;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r,a[i].id=i,b[i]=a[i];
	sort(a+1,a+n+1,CR);sort(b+1,b+n+1,CL);
	while(l<r)
	{
		int mi=(l+r)/2+1;
		Chk(mi)?l=mi:r=mi-1; 
	}
	for(int i=1;i<=min(m,l);i++)
	    ans[a[i].id]=ans[b[n-l+i].id]=i,v[a[i].id]=v[b[n-l+i].id]=1;
	for(int i=1;i<=n&&l<m;i++)if(!v[i])ans[i]=++l;
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9580kb

input:

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

output:

2 4 1 3 2 1 3

result:

ok answer = 7

Test #2:

score: 0
Accepted
time: 0ms
memory: 9524kb

input:

2 2
1 2
3 4

output:

1 1

result:

ok answer = 2

Test #3:

score: 0
Accepted
time: 1ms
memory: 5608kb

input:

2 1
1 2
2 3

output:

1 0

result:

ok answer = 1

Test #4:

score: 0
Accepted
time: 2ms
memory: 7528kb

input:

1 1
4 26

output:

1

result:

ok answer = 1

Test #5:

score: 0
Accepted
time: 2ms
memory: 9484kb

input:

500 258
1 3
3 5
2 4
3 5
4 5
4 5
1 4
1 2
3 5
2 5
2 5
4 5
4 5
4 5
2 3
1 4
1 4
1 4
4 5
4 5
2 3
4 5
3 5
3 5
1 5
1 4
2 5
1 5
3 5
3 4
4 5
2 3
3 5
3 5
4 5
2 3
1 5
1 5
2 3
2 3
3 4
3 5
3 4
1 3
1 2
1 5
4 5
2 3
2 4
1 3
4 5
4 5
4 5
1 3
3 5
4 5
3 5
1 5
1 2
1 2
3 5
3 5
4 5
3 4
3 5
2 3
2 5
2 4
2 5
3 5
2 3
1 5
4 5
...

output:

83 119 120 121 32 31 122 27 123 124 125 18 25 24 93 126 127 128 20 53 96 51 129 130 131 132 133 134 135 136 38 91 137 138 13 77 139 140 85 84 141 142 143 89 15 144 16 80 145 79 4 3 103 115 146 93 147 148 1 7 149 150 96 151 152 110 153 154 155 156 106 157 106 158 159 102 109 160 161 111 112 162 28 33...

result:

ok answer = 376

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 9588kb

input:

500 242
8 9
9 10
2 9
8 10
9 10
6 10
4 8
4 5
2 6
7 10
3 8
1 8
1 6
5 9
7 8
8 10
8 9
8 10
2 9
2 3
6 8
3 10
5 9
1 3
6 8
4 10
9 10
8 9
8 10
1 9
3 9
3 7
2 3
6 10
3 6
6 10
3 4
3 6
9 10
5 7
8 10
6 10
5 6
5 7
7 8
1 3
4 7
9 10
4 9
2 4
8 9
1 3
8 10
3 4
9 10
4 9
5 10
8 9
1 3
1 5
8 10
3 4
8 9
3 9
3 6
3 10
6 7
7 ...

output:

136 170 230 122 172 17 214 69 77 91 229 227 108 231 172 126 131 160 232 15 195 233 234 12 175 235 207 115 125 236 237 158 7 13 88 11 22 89 210 129 107 4 101 128 168 13 147 214 238 29 159 17 124 31 203 239 240 164 19 68 163 28 156 241 92 242 155 225 0 222 99 96 0 90 146 226 224 223 144 0 222 221 229 ...

result:

wrong answer participant answer = 437, judge answer = 471
English 繁體中文 简体中文

Server Time: 2024-11-29 16:44:32 | OpenSource Project