| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 392893 |
2021-04-22T07:46:53 Z |
Ruxandra985 |
Teams (CEOI11_tea) |
C++14 |
|
912 ms |
37960 KB |
#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;
int dp[DIMN];
int mp[DIMN];
int tt[DIMN];
struct idk{
int ech , ok , sz , fth;
} dp2[5010];
int w[DIMN] , poz[DIMN];
pair <int , int> v[DIMN];
FILE *fin = stdin;
FILE *fout = stdout;
int ok (int maxi , int n , int ok){
int now , a , b , st , dr , mid;
now = n;
while (now){ /// nu pare o idee buna ce fac....
a = max(0 , now - maxi); /// ma asigur ca v2 nu e -1
/// cea mai mica echipa posibila ar fi de v[now].first
b = now - v[now].first;
while (tt[b] == -1)
b--;
/// a <= b
if (a > b)
swap(a , b);
a = poz[a];
b = poz[b];
st = a;
dr = b;
while (st <= dr){
mid = (st + dr)/2;
if (dp[w[mid]] + 1 == dp[now])
dr = mid - 1;
else st = mid + 1;
}
if (ok){
fprintf (fout,"%d " , now - w[st]);
}
if (now - w[st] > maxi)
return 0;
while (now > w[st]){
if (ok){
fprintf (fout,"%d ",v[now].second);
//printf ("%d ",v[now].first);
}
now--;
}
if (ok){
fprintf (fout,"\n");
//printf ("\n");
}
}
return 1;
}
int main()
{
int n , i , st , dr , mid , elem , j , now;
fscanf (fin,"%d",&n);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i].first);
v[i].second = i;
}
sort (v + 1 , v + n + 1);
if (n <= 5000){
dp2[0].ok = 1;
for (i = 1 ; i <= n ; i++){
for (j = i - v[i].first ; j >= 0 ; j--){
if (!dp2[j].ok)
continue;
if (dp2[j].ech + 1 > dp2[i].ech){
dp2[i].ech = dp2[j].ech + 1;
dp2[i].ok = 1;
dp2[i].sz = max(i - j , dp2[j].sz);
dp2[i].fth = j;
}
else if (dp2[j].ech + 1 == dp2[i].ech && max(i - j , dp2[j].sz) < dp2[i].sz){
dp2[i].ech = dp2[j].ech + 1;
dp2[i].ok = 1;
dp2[i].sz = max(i - j , dp2[j].sz);
dp2[i].fth = j;
}
}
}
fprintf (fout,"%d\n" , dp2[n].ech);
now = n;
while (now){
fprintf (fout,"%d ", now - dp2[now].fth);
for (i = now ; i > dp2[now].fth ; i--)
fprintf (fout,"%d ",v[i].second);
fprintf (fout,"\n");
now = dp2[now].fth;
}
return 0;
}
elem = 0;
for (i = 1 ; i <= n ; i++){
if (i - v[i].first < 0){
dp[i] = -2000000000;
mp[i] = mp[i - 1];
tt[i] = -1;
}
else {
dp[i] = mp[i - v[i].first] + 1;
w[++elem] = i;
poz[i] = elem;
tt[i] = i - v[i].first;
mp[i] = max(mp[i - 1] , dp[i]);
}
}
fprintf (fout,"%d\n" , dp[n]);
st = v[n].first;
dr = n;
while (st <= dr){
mid = (st + dr)/2;
if (ok(mid , n , 0))
dr = mid - 1; /// merge, cauti mai mic
else st = mid + 1;
}
/// solutia e st (dim minima a echipei maxime)
//printf ("%d ",st);
ok(st , n , 1);
return 0;
}
Compilation message
tea.cpp: In function 'int main()':
tea.cpp:84:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | fscanf (fin,"%d",&n);
| ~~~~~~~^~~~~~~~~~~~~
tea.cpp:86:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | fscanf (fin,"%d",&v[i].first);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
460 KB |
Output is correct |
| 2 |
Correct |
15 ms |
564 KB |
Output is correct |
| 3 |
Correct |
17 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
460 KB |
Output is correct |
| 2 |
Correct |
11 ms |
444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
3256 KB |
Output is correct |
| 2 |
Correct |
28 ms |
3208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
3532 KB |
Output is correct |
| 2 |
Correct |
28 ms |
2976 KB |
Output is correct |
| 3 |
Correct |
32 ms |
3576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
267 ms |
26264 KB |
Output is correct |
| 2 |
Correct |
306 ms |
26436 KB |
Output is correct |
| 3 |
Correct |
271 ms |
25940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
362 ms |
34408 KB |
Output is correct |
| 2 |
Correct |
912 ms |
37960 KB |
Output is correct |
| 3 |
Correct |
411 ms |
35040 KB |
Output is correct |
| 4 |
Correct |
335 ms |
30788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
373 ms |
31720 KB |
Output is correct |
| 2 |
Correct |
288 ms |
27124 KB |
Output is correct |
| 3 |
Correct |
364 ms |
35012 KB |
Output is correct |
| 4 |
Correct |
382 ms |
35012 KB |
Output is correct |
