답안 #936667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936667	2024-03-02T13:14:18 Z	JuanJL	서열 (APIO23_sequence)	C++17	35 / 100	564 ms	90268 KB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define fst first 
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

ll n; 
vector<ll> a;


int sequence(int N, std::vector<int> A) {
	n=N;
	a.clear();
	a.resize(n);
	forn(i,0,n) a[i]=A[i];
	ll res = 0;
	
	if(n<=(2*pow(10,3))){
		//Subtasks 1 , 2
		forn(i,0,n){
			indexed_multiset im;
			ll ocurr[n+1];
			mset(ocurr,0);
			forn(j,i,n){
				im.insert(a[j]);
				ocurr[a[j]]++;
				
				res = max(res,ocurr[*im.find_by_order((SZ(im))/2)]);
				if(SZ(im)%2==0) res = max(res,ocurr[*im.find_by_order((SZ(im)/2)-1)]);

			}
		}
	}else{
		vector<vector<ll>> p;
		set<ll> vals;
		map<ll,ll> cI;
		forn(i,0,n) vals.insert(a[i]);
		ll ind = 0;
		for(auto i:vals) cI[i]=ind,ind++;
		p.resize(SZ(cI));
		forn(i,0,n)	p[cI[a[i]]].pb(i);
		
		ll men = 0;
		ll may = 0;
		ll igu = 0;
		forn(i,0,SZ(p)){
			men=0; may = 0; igu = 0;
			forn(j,0,SZ(p[i])){
				if(abs(p[i][j]-p[i][j+1])==1) igu++;
				else break;
			}
			igu++;
			res=max(res,igu);
			res=max(res,SZ(p[i])-(igu));
			if(SZ(p[i])==1) may = 0;
			else may = (p[i][igu]-p[i][igu-1])-1;
			
			men=p[i][0]+((n-1)-p[i][SZ(p[i])-1]);
			//cout<<SZ(p[i])<<" "<<may<<" "<<men<<'\n';
			if(may<=men+SZ(p[i])) res = max(res,(ll)SZ(p[i]));
			
			
			//cout<<res<<" "<<i<<'\n';
		}
	}
	return res;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	432 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	432 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	364 ms	548 KB	Output is correct
14	Correct	357 ms	344 KB	Output is correct
15	Correct	365 ms	348 KB	Output is correct
16	Correct	345 ms	348 KB	Output is correct
17	Correct	327 ms	344 KB	Output is correct
18	Correct	312 ms	348 KB	Output is correct
19	Correct	368 ms	600 KB	Output is correct
20	Correct	364 ms	552 KB	Output is correct
21	Correct	374 ms	540 KB	Output is correct
22	Correct	380 ms	548 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	255 ms	60896 KB	Output is correct
3	Correct	255 ms	60756 KB	Output is correct
4	Correct	43 ms	12296 KB	Output is correct
5	Correct	234 ms	55964 KB	Output is correct
6	Correct	235 ms	55884 KB	Output is correct
7	Correct	44 ms	12640 KB	Output is correct
8	Correct	44 ms	13136 KB	Output is correct
9	Correct	40 ms	13728 KB	Output is correct

Subtask #4
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	44 ms	15608 KB	Output is correct
3	Incorrect	45 ms	12472 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	564 ms	90268 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	432 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	364 ms	548 KB	Output is correct
14	Correct	357 ms	344 KB	Output is correct
15	Correct	365 ms	348 KB	Output is correct
16	Correct	345 ms	348 KB	Output is correct
17	Correct	327 ms	344 KB	Output is correct
18	Correct	312 ms	348 KB	Output is correct
19	Correct	368 ms	600 KB	Output is correct
20	Correct	364 ms	552 KB	Output is correct
21	Correct	374 ms	540 KB	Output is correct
22	Correct	380 ms	548 KB	Output is correct
23	Incorrect	54 ms	9916 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	432 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	364 ms	548 KB	Output is correct
14	Correct	357 ms	344 KB	Output is correct
15	Correct	365 ms	348 KB	Output is correct
16	Correct	345 ms	348 KB	Output is correct
17	Correct	327 ms	344 KB	Output is correct
18	Correct	312 ms	348 KB	Output is correct
19	Correct	368 ms	600 KB	Output is correct
20	Correct	364 ms	552 KB	Output is correct
21	Correct	374 ms	540 KB	Output is correct
22	Correct	380 ms	548 KB	Output is correct
23	Correct	255 ms	60896 KB	Output is correct
24	Correct	255 ms	60756 KB	Output is correct
25	Correct	43 ms	12296 KB	Output is correct
26	Correct	234 ms	55964 KB	Output is correct
27	Correct	235 ms	55884 KB	Output is correct
28	Correct	44 ms	12640 KB	Output is correct
29	Correct	44 ms	13136 KB	Output is correct
30	Correct	40 ms	13728 KB	Output is correct
31	Correct	44 ms	15608 KB	Output is correct
32	Incorrect	45 ms	12472 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

답안 #936667

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 17.0 / 17.0

Subtask #3 7.0 / 7.0

Subtask #4 0.0 / 12.0

Subtask #5 0.0 / 13.0

Subtask #6 0.0 / 22.0

Subtask #7 0.0 / 18.0

Subtask #1
11.0 / 11.0

Subtask #2
17.0 / 17.0

Subtask #3
7.0 / 7.0

Subtask #4
0.0 / 12.0

Subtask #5
0.0 / 13.0

Subtask #6
0.0 / 22.0

Subtask #7
0.0 / 18.0