oj.uz

Submission #290325

# Submission time Handle Problem Language Result Execution time Memory
290325 2020-09-03T15:57:59 Z beso123 Fun Tour (APIO20_fun) C++14
26 / 100
 2000 ms 16168 KB 
#include "fun.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int> get_pas(priority_queue<pii> s1,priority_queue<pii> s2){
    vector<int> ans;
    int d=1;
if(s2.size()>s1.size())
    d=2;
while(true){
        pii v;
    if(d==1){
        v=s1.top();
        s1.pop();
        ans.push_back(v.y);
    }
    else{
    v=s2.top();
        s2.pop();
        ans.push_back(v.y);
    }
    d=3-d;
    if(s1.size()==0 && s2.size()==0)
        break;
}
return ans;
}
bool check(priority_queue<pii> s1,priority_queue<pii> s2,priority_queue<pii> s3){
    if((int)s1.size()+(int)s2.size()==s3.size()){
        return true;
    }
    return false;
}
vector<int> off(priority_queue<pii> s1,priority_queue<pii> s2,priority_queue<pii> s3,int d){
    while(!s2.empty()){
        s1.push(s2.top());
        s2.pop();
    }
   if(d==-1)
   return get_pas(s3,s1);
   else return get_pas(s1,s3);
}
vector<int> createFunTour(int n,int Q1){
    if(n==2){
        return {0,1};
    }
int cnt=0,csize=INT_MAX;
for(int k=1;k<n;k++){
    int Size=attractionsBehind(0,k);
    if((Size-1)>=(n/2)){
        if(Size<csize){
            csize=Size;
            cnt=k;
        }
    }
}
vector<int> dist(n,0);
vector<int> P,al;
for(int k=0;k<n;k++){
    if(k==cnt)
        continue;
al.push_back(k);
    dist[k]=hoursRequired(k,cnt);
    if(dist[k]==1)
        P.push_back(k);
}
priority_queue<pii> s1,s2,s3;
for(int k=0;k<al.size();k++){
    int a=al[k];
    if(dist[a]==hoursRequired(P[0],a)+1){
            al[k]++;
        al[k]*=-1;
        s1.push({dist[a],a});
    }
}
for(int k=0;k<al.size();k++){
        if(al[k]<0)
        continue;
    int a=al[k];
    if(dist[a]==hoursRequired(P[1],a)+1){
            al[k]++;
        al[k]*=-1;
        s2.push({dist[a],a});
    }
}
if(P.size()!=2){
   for(int k=0;k<al.size();k++){
        if(al[k]<0)
        continue;
    int a=al[k];
    s3.push({dist[a],a});
}
}
vector<int> ans;
vector<int> p;
 
if(P.size()==2){
    ans=get_pas(s1,s2);
}
else{
    int cur=0;
      while(true){
   if(check(s1,s2,s3)){
       int d=1;
        if(cur!=3)
        d=-1;
    p=off(s1,s2,s3,d);
    break;
   }
      if(check(s3,s2,s1)){
           int d=1;
        if(cur!=1)
        d=-1;
    p=off(s3,s2,s1,d);
    break;
   }
      if(check(s1,s3,s2)){
           int d=1;
        if(cur!=2)
        d=-1;
    p=off(s1,s3,s2,d);
    break;
   }
    pii v1=s1.top(),v2=s2.top(),v3=s3.top();
    if(cur==1)
        v1.x=-1;
    if(cur==2)
        v2.x=-1;
    if(cur==3)
        v3.x=-1;
    int mn=max(v1.x,max(v2.x,v3.x));
    if(mn==v1.x){
        ans.push_back(v1.y);
        cur=1;
        s1.pop();
    }
    else
        if(mn==v2.x){
        ans.push_back(v2.y);
        cur=2;
        s2.pop();
    }
    else
        if(mn==v3.x){
        ans.push_back(v3.y);
        cur=3;
        s3.pop();
    }
    }
 
}
for(int k=0;k<p.size();k++)
    ans.push_back(p[k]);
ans.push_back(cnt);
 
return ans;
}

Compilation message

fun.cpp: In function 'bool check(std::priority_queue<std::pair<int, int> >, std::priority_queue<std::pair<int, int> >, std::priority_queue<std::pair<int, int> >)':
fun.cpp:31:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if((int)s1.size()+(int)s2.size()==s3.size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 | for(int k=0;k<al.size();k++){
      |             ~^~~~~~~~~~
fun.cpp:78:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 | for(int k=0;k<al.size();k++){
      |             ~^~~~~~~~~~
fun.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for(int k=0;k<al.size();k++){
      |                ~^~~~~~~~~~
fun.cpp:154:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 | for(int k=0;k<p.size();k++)
      |             ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 0 ms 256 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Execution timed out 2052 ms 16108 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 75 ms 1912 KB Output is correct
15 Execution timed out 2093 ms 16168 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 0 ms 256 KB Output is correct
19 Correct 0 ms 256 KB Output is correct
20 Correct 0 ms 256 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 0 ms 256 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 384 KB Output is correct
36 Correct 2 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Execution timed out 2052 ms 16108 KB Time limit exceeded
45 Halted 0 ms 0 KB -