Submission #1866564
Source Code Expand
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define MAXI 100000
#define u(x, a, b) for(ll x = a; x < b; x++)
#define d(x, a, b) for(ll x = a; x > b; x--)
vector<ll> sub(vector<ll> in, ll le, ll ri){
vector<ll> ans;
if(le == ri){
vector<ll> temp(MAXI, MAXI);
ans = temp;
return ans;
}
u(two, le, ri){
ans.push_back(in[two]);
}
return ans;
}
deque< pair<ll, ll> > greedy(vector<ll> in){
deque< pair<ll, ll> > ans;
ll s = in.size(), min1 = MAXI, tar1 = -1, min2 = MAXI, tar2 = -1;
if(s == MAXI){
ans.push_back(make_pair(MAXI, MAXI));
return ans;
}
for(ll one = 0; one < s; one+=2){
if(in[one] < min1){
tar1 = one;
min1 = in[one];
}
}
for(ll one = tar1+1; one < s; one+=2){
if(in[one] < min2){
tar2 = one;
min2 = in[one];
}
}
ans.push_back(make_pair(min1, min2));
vector<ll> v1 = sub(in, 0, tar1), v2 = sub(in, tar1+1, tar2), v3 = sub(in, tar2+1, s);
deque< pair<ll, ll> > a1 = greedy(v1), a2 = greedy(v2), a3 = greedy(v3);
ll y = MAXI;
if(!a1.empty()){
y = min(a1[0].first, y);
}
if(!a2.empty()){
y = min(a2[0].first, y);
}
if(!a3.empty()){
y = min(a3[0].first, y);
}
while(y < MAXI){
if(y == a1[0].first){
ans.push_back(a1[0]);
a1.pop_front();
}
else if(y == a2[0].first){
ans.push_back(a2[0]);
a2.pop_front();
}
else{
ans.push_back(a3[0]);
a3.pop_front();
}
y = MAXI;
if(!a1.empty()){
y = min(a1[0].first, y);
}
if(!a2.empty()){
y = min(a2[0].first, y);
}
if(!a3.empty()){
y = min(a3[0].first, y);
}
}
return ans;
}
int main(){
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll n, temp;
cin >> n;
vector<ll> arr;
u(three, 0, n){
cin >> temp;
arr.push_back(temp);
}
deque< pair<ll, ll> > fin = greedy(arr);
u(three, 0, n/2){
cout << fin[three].first << ' ' << fin[three].second << ' ';
}
}
Submission Info
Submission Time |
|
Task |
E - Young Maids |
User |
vjudge2 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2393 Byte |
Status |
RE |
Exec Time |
2393 ms |
Memory |
6460 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 800 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
4 ms |
5744 KB |
0_01.txt |
AC |
3 ms |
3312 KB |
0_02.txt |
AC |
6 ms |
6460 KB |
1_00.txt |
AC |
3 ms |
3312 KB |
1_01.txt |
AC |
3 ms |
3312 KB |
1_02.txt |
TLE |
2301 ms |
-1094076 KB |
1_03.txt |
TLE |
2311 ms |
-888136 KB |
1_04.txt |
TLE |
2302 ms |
-1023432 KB |
1_05.txt |
TLE |
2332 ms |
-513732 KB |
1_06.txt |
RE |
2028 ms |
-510844 KB |
1_07.txt |
TLE |
2393 ms |
-511644 KB |
1_08.txt |
TLE |
2332 ms |
-513540 KB |
1_09.txt |
TLE |
2290 ms |
-1127348 KB |
1_10.txt |
TLE |
2298 ms |
-1015112 KB |
1_11.txt |
TLE |
2293 ms |
-1094700 KB |
1_12.txt |
TLE |
2337 ms |
-516356 KB |
1_13.txt |
RE |
2018 ms |
-510008 KB |
1_14.txt |
TLE |
2333 ms |
-513316 KB |
1_15.txt |
RE |
2001 ms |
-510860 KB |
1_16.txt |
TLE |
2332 ms |
-513196 KB |
1_17.txt |
RE |
2015 ms |
-511344 KB |
1_18.txt |
TLE |
2371 ms |
-513432 KB |
1_19.txt |
RE |
2017 ms |
-511488 KB |