Submission #889023

#TimeUsernameProblemLanguageResultExecution timeMemory
889023nnhzzzCipele (COCI18_cipele)C++14
72 / 90
73 ms16164 KiB
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <locale> #include <map> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> #include <chrono> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) (((i)>>(j))&1LL) #define MASK(i) (1LL<<(i)) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define fi first #define se second #define ll long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) #define endl "\n" #define MP make_pair #define int ll //-----------------------------------------------------------------------------------------------// int readInt(){ char c; do{ c = getchar(); }while(c!='-' && !isdigit(c)); bool neg = (c=='-'); int res = neg?0:c-'0'; while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0'); return neg?-res:res; } //------------------------------------------------------------------------------------------------// const ll LINF = 1e18; const int INF = 1e9; const int LOG = 20; const int MAXN = 5e5+7; const int N = 1e2+3; const int MOD = 1e9+7; const int BASE = 1e5; const ld EPS = 1e-9; const ld PI = acos(-1); const int OFFSET = 1e3; //------------------------------------------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } //------------------------------------------------------------------------------------------------// /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ int a[MAXN],b[MAXN]; int n,m; namespace sub1{ void solve(){ multiset<int> s1,s2; REP(i,1,n) s1.insert(a[i]); REP(i,1,m) s2.insert(b[i]); int res = 0; REP(i,1,n){ int val = *s1.begin(); s1.erase(s1.begin()); set<int>::iterator it1 = s2.lower_bound(val); if(it1==s2.end()) --it1; set<int>::iterator it2 = it1; if(it2!=s2.begin()) --it2; if(abs(*it1-val)<abs(val-*it2)){ maxi(res,abs(*it1-val)); s2.erase(it1); }else{ maxi(res,abs(val-*it2)); s2.erase(it2); } } cout << res; } } namespace sub3{ bool ok(int mid){ int j = 1; REP(i,1,n){ while(j<=m && abs(b[j]-a[i])>mid) ++j; if(j>m) return false; ++j; } return true; } void solve(){ sort(a+1,a+n+1); sort(b+1,b+m+1); int l = 0,r = INF,res = INF; while(l<=r){ int mid = (l+r)>>1; if(ok(mid)==true){ r = mid-1; res = mid; }else{ l = mid+1; } } cout << res; } } void solve(){ cin >> n >> m; REP(i,1,n) cin >> a[i]; REP(i,1,m) cin >> b[i]; if(n>m){ REP(i,1,n) swap(a[i],b[i]); swap(n,m); } if(n==m){ sub1::solve(); return ; } sub3::solve(); } __nnhzzz__{ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "test" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } #define task1 "nnhzzz" if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

cipele.cpp: In function 'int main()':
cipele.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cipele.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cipele.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cipele.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...