제출 #1036450

#제출 시각아이디문제언어결과실행 시간메모리
10364508pete8마상시합 토너먼트 (IOI12_tournament)C++17
100 / 100
86 ms34392 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<cassert> #include<unordered_map> #include <queue> #include <cstdint> #include<cstring> #include<limits.h> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> #include<bitset> using namespace std; #define ll long long #define f first #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-lopps") //#define int long long using namespace std; const int mod=1e9+7,mxn=2e5+5,inf=1e9,minf=-1e9,lg=25; int n,m,k,q; vector<pii>v; vector<int>adj[mxn+10]; int val[mxn+10],id[mxn+10],node; struct fen{ int fwk[mxn+10]; void init(){for(int i=0;i<=n;i++)fwk[i]=0;} void update(int pos,int val){ pos++; for(int i=pos;i<=n;i+=(i&-i))fwk[i]+=val; } int get(int x){ int pos=0,sum=0; for(int i=lg;i>=0;i--){ if(pos+(1LL<<i)<=n&&fwk[pos+(1LL<<i)]+sum<x){ pos+=(1LL<<i); sum+=fwk[pos]; } } return pos; } }t; int dp[mxn+10],dp2[mxn+10];//normal dp,and shifted dp void solve(int cur){ if(cur<n){ dp[cur]=val[cur]; if(cur)dp2[cur]=val[cur-1]; else dp2[cur]=k; } for(auto i:adj[cur]){ solve(i); dp[cur]=max(dp[cur],dp[i]),dp2[cur]=max(dp2[cur],dp2[i]); } } int add[mxn+10]; void solve2(int cur){ vector<int>pref,suf; for(auto i:adj[cur])pref.pb(dp[i]),suf.pb(dp2[i]); suf.pb(-1); for(int i=adj[cur].size()-1;i>=0;i--)suf[i]=max(suf[i],suf[i+1]); int l=-1; for(int i=0;i<adj[cur].size();i++){ if(k>=max(l,suf[i+1]))add[adj[cur][i]]+=add[cur]+1; l=max(l,pref[i]); } for(auto i:adj[cur])solve2(i); } bool repeat=0; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){ //will this work?? //if(repeat)assert(0); //repeat=1; t.init(); v.clear(); n=N,q=C; R=min(R,n); k=R; for(int i=0;i<C;i++,S++,E++)v.pb({*S,*E}); for(int i=0;i<n-1;i++,K++)val[i]=(*K); val[n-1]=k; for(int i=0;i<n;i++){ if(i)t.update(i,1); id[i]=i; } node=n; for(auto i:v){ vector<int>up; for(int j=i.f;j<=i.s;j++){ int x=t.get(j); adj[node].pb(id[x]); id[x]=node; if(j!=i.f)up.pb(x); } node++; for(auto j:up)t.update(j,-1); } node--; solve(node); solve2(node); int ans=0; for(int i=0;i<n;i++)if(add[i]>add[ans])ans=i; for(int i=0;i<=n;i++)adj[i].clear(),add[i]=0; //cout<<ans<<"LL\n"; return ans; }

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

tournament.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
tournament.cpp:42:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 |   void init(){for(int i=0;i<=n;i++)fwk[i]=0;}
      |             ^
tournament.cpp:43:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   43 |   void update(int pos,int val){
      |                              ^
tournament.cpp:47:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 |   int get(int x){
      |                ^
tournament.cpp:59:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 | void solve(int cur){
      |                   ^
tournament.cpp:71:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   71 | void solve2(int cur){
      |                    ^
tournament.cpp: In function 'void solve2(int)':
tournament.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0;i<adj[cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~
tournament.cpp: At global scope:
tournament.cpp:84:64: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   84 | int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
      |                                                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...