Submission #203194

#TimeUsernameProblemLanguageResultExecution timeMemory
203194MKopchevSticks (POI11_pat)C++14
68 / 100
406 ms45772 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=1e6+42,inf=2e9+42; int k; pair<int/*length*/,int/*colour*/> inp[nmax]; int pointer; vector<int> seen[nmax]; int last_seen[nmax]; bool is_less(pair<int/*length*/,int/*colour*/> a,pair<int/*length*/,int/*colour*/> b) { return a.first<b.first; } int furthest(int colour,int up_to) { int ok=0,not_ok=seen[colour].size(); while(not_ok-ok>1) { int av=(ok+not_ok)/2; if(seen[colour][av]<=up_to)ok=av; else not_ok=av; } return seen[colour][ok]; } int main() { scanf("%i",&k); int SZ,current; for(int i=1;i<=k;i++) { scanf("%i",&SZ); for(int j=1;j<=SZ;j++) { scanf("%i",&current); seen[i].push_back(current); pointer++; inp[pointer]={current,i}; } sort(seen[i].begin(),seen[i].end()); } for(int i=1;i<=k;i++)last_seen[i]=inf; sort(inp+1,inp+pointer+1); for(int i=pointer;i>=1;i--) { pair<int/*length*/,int/*colour*/> best={inf,0},second_best={inf,0},current; for(int j=1;j<=k;j++) if(j!=inp[i].second) { current={last_seen[j],j}; if(is_less(current,best))second_best=best,best=current; else if(is_less(current,second_best))second_best=current; } if(second_best.first<inf) { best.first=furthest(best.second,second_best.first); if(inp[i].first+best.first>second_best.first) { printf("%i %i %i %i %i %i\n",inp[i].second,inp[i].first,best.second,best.first,second_best.second,second_best.first); return 0; } } last_seen[inp[i].second]=inp[i].first; } printf("NIE\n"); return 0; }

Compilation message (stderr)

pat.cpp: In function 'int main()':
pat.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&k);
     ~~~~~^~~~~~~~~
pat.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&SZ);
         ~~~~~^~~~~~~~~~
pat.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&current);
             ~~~~~^~~~~~~~~~~~~~~
#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...
#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...