# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
257019 |
2020-08-03T14:02:12 Z |
Nucleist |
Gap (APIO16_gap) |
C++14 |
|
104 ms |
5880 KB |
//Self-control leads to consistency.
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
ll findGap(int T,int N){
if(T==2){
ll mx=0,mn=0;
ll dol=pow(10,18);
MinMax(0,dol,&mn,&mx);
ll l=mn+1,r=mx-1;
set<ll>ans;
ans.insert(mn),ans.insert(mx);
ll f=(r-l+1)/(N-1);
for (ll i = l; i <= r; i+=(f+1))
{
ll k=i,k1=i+f;
if(i+f>r){
k1=r;
}
MinMax(k,k1,&mn,&mx);
ans.insert(mn),ans.insert(mx);
if(i+f>r){
break;
}
}
ll sol=0;
ans.erase(-1);
ll last=*(ans.begin());
for(auto it:ans){
if(last!=it){
sol=max(sol,it-last);
last=it;
}
}
return sol;
}
set<ll>cur;
ll mx=0,mn=0;
ll l=0,r=pow(10,18);
while(sz(cur)<N){
MinMax(l,r,&mn,&mx);
cur.insert(mn),cur.insert(mx);
cur.erase(-1);
l=mn+1,r=mx-1;
}
ll sol=0;
ll last=*(cur.begin());
for(auto it:cur){
if(last!=it){
sol=max(sol,it-last);
last=it;
}
}
return sol;
}
Compilation message
gap.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
gap.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
gap.cpp: In function 'void setIO(std::__cxx11::string)':
gap.cpp:29:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen((s+".in").c_str(),"r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gap.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen((s+".out").c_str(),"w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
17 ms |
1656 KB |
Output is correct |
17 |
Correct |
17 ms |
1656 KB |
Output is correct |
18 |
Correct |
17 ms |
1656 KB |
Output is correct |
19 |
Correct |
18 ms |
1648 KB |
Output is correct |
20 |
Correct |
15 ms |
1656 KB |
Output is correct |
21 |
Correct |
79 ms |
5752 KB |
Output is correct |
22 |
Correct |
82 ms |
5744 KB |
Output is correct |
23 |
Correct |
76 ms |
5752 KB |
Output is correct |
24 |
Correct |
81 ms |
5880 KB |
Output is correct |
25 |
Correct |
69 ms |
5756 KB |
Output is correct |
26 |
Correct |
86 ms |
5752 KB |
Output is correct |
27 |
Correct |
85 ms |
5752 KB |
Output is correct |
28 |
Correct |
86 ms |
5752 KB |
Output is correct |
29 |
Correct |
77 ms |
5752 KB |
Output is correct |
30 |
Correct |
68 ms |
5752 KB |
Output is correct |
31 |
Correct |
0 ms |
384 KB |
Output is correct |
32 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
22 ms |
1536 KB |
Output is correct |
17 |
Correct |
21 ms |
1536 KB |
Output is correct |
18 |
Correct |
22 ms |
1536 KB |
Output is correct |
19 |
Correct |
22 ms |
1528 KB |
Output is correct |
20 |
Correct |
8 ms |
640 KB |
Output is correct |
21 |
Correct |
104 ms |
5240 KB |
Output is correct |
22 |
Correct |
104 ms |
5240 KB |
Output is correct |
23 |
Correct |
96 ms |
5364 KB |
Output is correct |
24 |
Correct |
94 ms |
5368 KB |
Output is correct |
25 |
Correct |
92 ms |
5752 KB |
Output is correct |
26 |
Correct |
94 ms |
5356 KB |
Output is correct |
27 |
Correct |
97 ms |
5368 KB |
Output is correct |
28 |
Correct |
98 ms |
5352 KB |
Output is correct |
29 |
Correct |
97 ms |
5240 KB |
Output is correct |
30 |
Correct |
41 ms |
1912 KB |
Output is correct |
31 |
Correct |
0 ms |
384 KB |
Output is correct |
32 |
Correct |
0 ms |
384 KB |
Output is correct |