제출 #807699

#제출 시각아이디문제언어결과실행 시간메모리
807699I_Love_EliskaM_식물 비교 (IOI20_plants)C++17
43 / 100
3025 ms15012 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; #define forn(i,_n) for(int i=0;i<_n;++i) #define all(x) x.begin(),x.end() #define pb push_back #define pi pair<int,int> #define f first #define s second using ll = long long; const int N=2e5+55; int p[N], L[N], R[N]; int n; int k; struct sgt { vector<int> t,lazy; int sz=1; sgt(int n) { while (sz<n) sz<<=1; t.assign(2*sz,0); lazy.assign(4*sz,0); } void push(int v) { t[v]+=lazy[v]; lazy[2*v+1]+=lazy[v]; lazy[2*v+2]+=lazy[v]; lazy[v]=0; } void add(int v, int l, int r, int lx, int rx, int x) { if (lazy[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { lazy[v]+=x; push(v); return; } int m=(l+r)>>1; add(2*v+1,l,m,lx,rx,x); add(2*v+2,m,r,lx,rx,x); t[v]=max(t[2*v+1],t[2*v+2]); } void add(int l, int r, int x) { add(0,0,sz,l,r,x); } int query(int v, int l, int r, int lx, int rx) { if (lazy[v]) push(v); if (rx<=l || r<=lx) return -1e9-7; if (lx<=l && r<=rx) return t[v]; int m=(l+r)>>1; int lq=query(2*v+1,l,m,lx,rx); int rq=query(2*v+2,m,r,lx,rx); t[v]=max(t[2*v+1],t[2*v+2]); return max(lq,rq); } int query(int l, int r) { return query(0,0,sz,l,r); } }; sgt st(N); vector<int> adj[305]; int vis[305]; bitset<305> bs[305]; void dfs(int u) { if (vis[u]==1) assert(0); if (vis[u]) return; bs[u][u]=1; vis[u]=1; for(auto&v:adj[u]) { dfs(v); bs[u]|=bs[v]; } vis[u]=2; } void init(int _k, vector<int> r) { k=_k; n=r.size(); if (n<=300) { forn(i,n) r[i]=k-1-r[i]; forn(i,n) r.pb(r[i]); forn(i,n) r.pb(r[i]); forn(it,n) { for (int i=n; i<2*n; ++i) { if (r[i]==k-1) { int z=i; for (int j=i; j>z-k; --j) if (r[j]==k-1) z=j; for (int j=z+1; j<z+k; ++j) { if (vis[j%n]) adj[j%n].pb(z%n); else adj[z%n].pb(j%n); } vis[z%n]=1; r[z%n]=-1e9; for (int j=z; j>z-k; --j) { r[(j%n)]++; r[(j%n)+n]++; r[(j%n)+2*n]++; } break; } } } forn(i,n) vis[i]=0; forn(i,n) dfs(i); return; } if (k==2) { int z=0; forn(i,n) r[i]^=1; forn(i,n) if (r[i]==0) z=i; for (int i=z+n; i>z; --i) { if (r[i%n]) R[i%n]=R[(i+1)%n]; else R[i%n]=i%n; } z=0; forn(i,n) if (r[i]) z=i; ++z; for (int i=z; i<z+n; ++i) { if (r[(i-1+n)%n]) L[i%n]=i%n; else L[i%n]=L[(i-1+n)%n]; } forn(i,n) { L[i]+=n, R[i]+=n; } forn(i,n) { if (L[i]==R[i] && L[i]==i+n) continue; if (L[i]>=R[i]) L[i]-=n; } return; } if (2*k>n) { forn(i,n) st.add(i,i+1,r[i]); forn(i,n) { int l=0, r=n-1; while (l<r) { int mid=(l+r+1)>>1; int x=st.query(mid,n); if (x!=k-1) r=mid-1; else l=mid; } int z=r; l=0, r=k; while (l<r) { int mid=(l+r)>>1; int f=z-k+1; int x; if (f>=0) { x=st.query(f,f+mid+1); } else { if (f+mid+1>0) { x=max(st.query(f+n,n),st.query(0,f+mid+1)); } else { x=st.query(f+n,f+mid+1+n); } } if (x==k-1) r=mid; else l=mid+1; } z=z-k+1+r; if (z<0) z+=n; p[z]=i; st.add(z,z+1,-k); int f=z-k+1; if (f>=0) { st.add(f,z,1); } else { st.add(0,z,1); st.add(n+f,n,1); } } return; } //vector<int> pr(2*n+1,0); //forn(i,2*n) pr[i+1]=pr[i]+(r[i]==0); } int compare_plants(int x, int y) { if (n<=300) { if (bs[x][y]) { return 1; } if (bs[y][x]) { return -1; } return 0; } if (k==2) { if (L[x]<=y && y<=R[x]) return 1; if (L[x]<=y+n && y+n<=R[x]) return 1; swap(x,y); if (L[x]<=y && y<=R[x]) return -1; if (L[x]<=y+n && y+n<=R[x]) return -1; return 0; } if (2*k>n) { if (p[x]>p[y]) return 1; else return -1; } }

컴파일 시 표준 에러 (stderr) 메시지

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:208:1: warning: control reaches end of non-void function [-Wreturn-type]
  208 | }
      | ^
#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...