Submission #1518186
Source Code Expand
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
bool f(vl& a, ll x) {
int n = sz(a), m = n+1;
ll s = 0;
rep(i,n) {
ll d = a[i]+x-(n-1);
s += (d+m-1)/m;
if (s > x) return false;
}
return true;
}
int main() {
int n;
scanf("%d",&n);
vl a(n);
cin>>a;
ll ans = LINF;
rep(i,n) {
ll l = -1, r = 1e16; r *= 2;
while (l+1<r) {
ll c = (l+r)/2;
if (f(a,c*n)) r = c; else l = c;
}
mins(ans,r*n+i);
sort(rng(a));
rep(j,n) a[j]++;
a.back() -= n+1;
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time
2017-08-18 03:45:42+0900
Task
E - Decrease (Judge ver.)
User
snuke
Language
C++14 (GCC 5.4.1)
Score
600
Code Size
2425 Byte
Status
AC
Exec Time
3 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:62:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
600 / 600
Status
Set Name
Test Cases
Sample
example0, example1, example2, example3, example4
All
example0, example1, example2, example3, example4, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, small0, small1, small2, small3, small4, small5, small6, small7, small8, small9
Case Name
Status
Exec Time
Memory
example0
AC
1 ms
256 KB
example1
AC
1 ms
256 KB
example2
AC
1 ms
256 KB
example3
AC
1 ms
256 KB
example4
AC
1 ms
256 KB
maxrand0
AC
1 ms
256 KB
maxrand1
AC
3 ms
256 KB
maxrand2
AC
1 ms
256 KB
maxrand3
AC
3 ms
256 KB
maxrand4
AC
1 ms
256 KB
maxrand5
AC
3 ms
256 KB
maxrand6
AC
1 ms
256 KB
maxrand7
AC
3 ms
256 KB
maxrand8
AC
1 ms
256 KB
maxrand9
AC
2 ms
256 KB
rand0
AC
1 ms
256 KB
rand1
AC
1 ms
256 KB
rand2
AC
2 ms
256 KB
rand3
AC
2 ms
256 KB
rand4
AC
1 ms
256 KB
rand5
AC
1 ms
256 KB
rand6
AC
1 ms
256 KB
rand7
AC
2 ms
256 KB
rand8
AC
1 ms
256 KB
rand9
AC
1 ms
256 KB
small0
AC
1 ms
256 KB
small1
AC
2 ms
256 KB
small2
AC
1 ms
256 KB
small3
AC
1 ms
256 KB
small4
AC
2 ms
256 KB
small5
AC
2 ms
256 KB
small6
AC
2 ms
256 KB
small7
AC
1 ms
256 KB
small8
AC
2 ms
256 KB
small9
AC
2 ms
256 KB