Submission #1866605
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 200020
#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){
ans.push_back(0);
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 == 1){
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(!a1.empty()){
if(y == a1[0].first){
ans.push_back(a1[0]);
a1.pop_front();
}
}
if(!a2.empty()){
if(y == a2[0].first){
ans.push_back(a2[0]);
a2.pop_front();
}
}
if(!a3.empty()){
if(y == a3[0].first){
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 |
vjudge1 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2519 Byte |
Status |
TLE |
Exec Time |
2265 ms |
Memory |
2092080 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 |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
TLE |
2259 ms |
-1819656 KB |
1_03.txt |
TLE |
2244 ms |
-2076248 KB |
1_04.txt |
TLE |
2265 ms |
-1710296 KB |
1_05.txt |
AC |
165 ms |
10580 KB |
1_06.txt |
AC |
189 ms |
14164 KB |
1_07.txt |
AC |
185 ms |
14292 KB |
1_08.txt |
AC |
189 ms |
14164 KB |
1_09.txt |
TLE |
2245 ms |
2092080 KB |
1_10.txt |
TLE |
2264 ms |
-1712456 KB |
1_11.txt |
TLE |
2257 ms |
-1881692 KB |
1_12.txt |
AC |
170 ms |
11404 KB |
1_13.txt |
AC |
178 ms |
11352 KB |
1_14.txt |
AC |
176 ms |
10472 KB |
1_15.txt |
AC |
177 ms |
12252 KB |
1_16.txt |
AC |
183 ms |
15456 KB |
1_17.txt |
AC |
175 ms |
9684 KB |
1_18.txt |
AC |
176 ms |
11360 KB |
1_19.txt |
AC |
184 ms |
17384 KB |