Submission #477516

#TimeUsernameProblemLanguageResultExecution timeMemory
477516nicolaalexandraXylophone (JOI18_xylophone)C++14
100 / 100
60 ms544 KiB
#include <bits/stdc++.h> #include "xylophone.h" #define DIM 5010 using namespace std; int v[DIM],a[DIM],f[DIM]; int n,i,pas; /* void answer (int i, int val){ //cout<<i<<" "<<val<<"\n"; cout<<val<<"\n"; } int query (int x, int y){ pas++; int maxi = 0, mini = n+1; for (int i=x;i<=y;i++){ mini = min (mini,a[i]); maxi = max (maxi,a[i]); } return maxi - mini; } */ void solve (int n){ /// determin pozitia lui n int st = 1, dr = n, sol_poz; while (st <= dr){ int mid = (st+dr)>>1; if (query(1,mid) == n-1){ sol_poz = mid; dr = mid-1; } else st = mid+1; } v[sol_poz] = n; /*divide (1,sol_poz-1,n,1,1); divide (sol_poz+1,n,n,1,0); */ f[n] = 1; if (sol_poz > 1){ v[sol_poz-1] = n - query (sol_poz-1,sol_poz); f[v[sol_poz-1]] = 1; } if (sol_poz < n){ v[sol_poz+1] = n - query (sol_poz,sol_poz+1); f[v[sol_poz+1]] = 1; } for (i=sol_poz-2;i>=1;i--){ int dif = query (i,i+1); if (v[i+1] - dif <= 0){ v[i] = v[i+1] + dif; f[v[i]] = 1; continue; } if (v[i+1] + dif > n){ v[i] = v[i+1] - dif; f[v[i]] = 1; continue; } if (!f[v[i+1]-dif] && !f[v[i+1]+dif]){ /// am doua variante posibile int dif2 = query (i,i+2); int val = v[i+1] + dif; if (max(val,max(v[i+1],v[i+2])) - min (val,min(v[i+1],v[i+2])) == dif2) v[i] = val; else v[i] = v[i+1] - dif; /* if (dif2 == max(v[i+1],v[i+2]) - min(v[i+1],v[i+2])){ if (v[i+1] < v[i+2]) v[i] = v[i+1] + dif; else v[i] = v[i-1] - dif; } else { if (dif2 == dif){ if (v[i+1] < v[i+2]) v[i] = v[i+1] + dif; else v[i] = v[i+1] - dif; } else { if (v[i+1] < v[i+2]) v[i] = v[i+1] - dif; else v[i] = v[i+1] + dif; } } */ f[v[i]] = 1; continue; } if (!f[v[i+1]-dif]){ v[i] = v[i+1] - dif; f[v[i]] = 1; } else { v[i] = v[i+1] + dif; f[v[i]] = 1; } } for (i=sol_poz+2;i<=n;i++){ int dif = query (i-1,i); if (v[i-1] - dif <= 0){ v[i] = v[i-1] + dif; f[v[i]] = 1; continue; } if (v[i-1] + dif > n){ v[i] = v[i-1] - dif; f[v[i]] = 1; continue; } if (!f[v[i-1]-dif] && !f[v[i-1]+dif]){ int dif2 = query (i-2,i); if (max(v[i-1]+dif,max(v[i-1],v[i-2])) - min(v[i-1]+dif,min(v[i-1],v[i-2])) == dif2) v[i] = v[i-1] + dif; else v[i] = v[i-1] - dif; f[v[i]] = 1; continue; } if (!f[v[i-1]-dif]){ v[i] = v[i-1] - dif; f[v[i]] = 1; } else { v[i] = v[i-1] + dif; f[v[i]] = 1; } } for (int i=1;i<=n;i++) answer (i,v[i]); } /* int main (){ ifstream cin ("date.in"); ofstream cout ("date.out"); cin>>n; for (i=1;i<=n;i++) cin>>a[i]; solve (n); cout<<pas; return 0; } */

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:51:34: warning: 'sol_poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         v[sol_poz+1] = n - query (sol_poz,sol_poz+1);
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...