QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358931#6553. Shared Memory Switchucup-team266RE 1ms3832kbC++231.5kb2024-03-20 09:05:092024-03-20 09:05:09

Judging History

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

  • [2024-03-20 09:05:09]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3832kb
  • [2024-03-20 09:05:09]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int used[200200];
int q[200200];
bool flag[200200];
int delta[200200];
vector<int> st[200200];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,b;
	cin>>n>>b;
	for(int i=1;i<=n;i++)
		cin>>q[i];
	int s=0;
	vector<int> vec;
	for(int i=n;i>=1;i--)
		if(q[i]==-1)
		{
			s++;
			for(int x=1;x<=n;x++)
				st[x].pb(i);
		}
		else
		{
			if(used[q[i]]<s)
			{
				vec.pb(i);
				used[q[i]]++;
				delta[i]++;
				delta[st[q[i]].back()]--;
				st[q[i]].pop_back();
			}
			else
				flag[i]=1;
		}
	vector<int> vec2;
	for(int i=1;i<=n;i++)
	{
		delta[i]+=delta[i-1];
		if(flag[i])
			vec2.pb(i);
		while(sz(vec2)>b-delta[i])
			vec2.pop_back();
	}
	for(auto x:vec2)
		vec.pb(x);
	cout<<sz(vec)<<'\n';
	for(auto x:vec)
		cout<<x<<" ";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

14 5
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1

output:

9
12 10 8 6 5 4 3 1 14 

result:

ok n=14

Test #2:

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

input:

14 4
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1

output:

8
12 10 8 6 5 4 3 14 

result:

ok n=14

Test #3:

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

input:

0 0

output:

0

result:

ok n=0

Test #4:

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

input:

0 1

output:

0

result:

ok n=0

Test #5:

score: -100
Runtime Error

input:

3 0
1 -1 2

output:


result: