oj.uz

Submission #1013468

# Submission time Handle Problem Language Result Execution time Memory
1013468 2024-07-03T14:50:45 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2012 KB 
// #include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define endl "\n"
using ull=unsigned long long;
using ll=long long;
using pii=pair<int,int>;
const int mod=1e9+7;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mxn=2e5+100;
vector<int> v;
int n;
vector<int> countScans(vector<int> A,vector<int> x,vector<int> y){
	v=A;
	n=v.size();
	int q=x.size();
	vector<int> Ans(q);
	auto dist = [&](int x,int a,int b){
		return min((x-a),(x-b));
	};
	for(int i=0;i<q;i++){
		vector<int> c=v;
		c[x[i]]=y[i];
		vector<int> t=c;
		sort(all(c));
		int ans=0;
		map<int,int> a,b;
		for(int i=0;i<n;i++){
			if(a.count(c[i])==0){
				a[c[i]]=i;
			}
			b[c[i]]=i;
		}
		for(int i=0;i<n;i++){
			ans=max(ans,dist(i,a[t[i]],b[t[i]]));
		}
		Ans[i]=ans;
		v=t;
	}
	return Ans;
}



#ifdef IOI
// #include "bubblesort2.h"

// #include <cstdio>
// #include <cstdlib>
// #include <vector>

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
	
	vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}

#endif

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 344 KB Output is correct
2 Correct 194 ms 348 KB Output is correct
3 Correct 1182 ms 728 KB Output is correct
4 Correct 1166 ms 716 KB Output is correct
5 Correct 1145 ms 720 KB Output is correct
6 Correct 955 ms 716 KB Output is correct
7 Correct 1071 ms 720 KB Output is correct
8 Correct 1100 ms 716 KB Output is correct
9 Correct 1045 ms 720 KB Output is correct
10 Correct 948 ms 604 KB Output is correct
11 Correct 944 ms 600 KB Output is correct
12 Correct 923 ms 720 KB Output is correct
13 Correct 938 ms 712 KB Output is correct
14 Correct 915 ms 600 KB Output is correct
15 Correct 1036 ms 712 KB Output is correct
16 Correct 1020 ms 708 KB Output is correct
17 Correct 1041 ms 708 KB Output is correct
18 Correct 1008 ms 856 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 344 KB Output is correct
2 Correct 194 ms 348 KB Output is correct
3 Correct 1182 ms 728 KB Output is correct
4 Correct 1166 ms 716 KB Output is correct
5 Correct 1145 ms 720 KB Output is correct
6 Correct 955 ms 716 KB Output is correct
7 Correct 1071 ms 720 KB Output is correct
8 Correct 1100 ms 716 KB Output is correct
9 Correct 1045 ms 720 KB Output is correct
10 Correct 948 ms 604 KB Output is correct
11 Correct 944 ms 600 KB Output is correct
12 Correct 923 ms 720 KB Output is correct
13 Correct 938 ms 712 KB Output is correct
14 Correct 915 ms 600 KB Output is correct
15 Correct 1036 ms 712 KB Output is correct
16 Correct 1020 ms 708 KB Output is correct
17 Correct 1041 ms 708 KB Output is correct
18 Correct 1008 ms 856 KB Output is correct
19 Execution timed out 9036 ms 1372 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4860 ms 1100 KB Output is correct
2 Execution timed out 9068 ms 2012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 344 KB Output is correct
2 Correct 194 ms 348 KB Output is correct
3 Correct 1182 ms 728 KB Output is correct
4 Correct 1166 ms 716 KB Output is correct
5 Correct 1145 ms 720 KB Output is correct
6 Correct 955 ms 716 KB Output is correct
7 Correct 1071 ms 720 KB Output is correct
8 Correct 1100 ms 716 KB Output is correct
9 Correct 1045 ms 720 KB Output is correct
10 Correct 948 ms 604 KB Output is correct
11 Correct 944 ms 600 KB Output is correct
12 Correct 923 ms 720 KB Output is correct
13 Correct 938 ms 712 KB Output is correct
14 Correct 915 ms 600 KB Output is correct
15 Correct 1036 ms 712 KB Output is correct
16 Correct 1020 ms 708 KB Output is correct
17 Correct 1041 ms 708 KB Output is correct
18 Correct 1008 ms 856 KB Output is correct
19 Execution timed out 9036 ms 1372 KB Time limit exceeded
20 Halted 0 ms 0 KB -