oj.uz

Submission #303285

# Submission time Handle Problem Language Result Execution time Memory
303285 2020-09-20T07:08:00 Z daniel920712 Comparing Plants (IOI20_plants) C++14
19 / 100
 4000 ms 20732 KB 
#include "plants.h"
#include <stdio.h>
#include <vector>
#include <utility>
#include <set>
using namespace std;
vector < int > all;
vector < int > Next[200005];
vector < pair < int , int > > con[200005];
int N,tt=0;
bool use[2000005]={0};
int Con[200005];
int what[200005];

void init(int k,vector<int> r)
{
    int a=0,b=0,i,j,ok=0,l,t,t2,x;
    all=r;
    N=r.size();
    if(k==2) tt=1;
    for(i=0;i<N;i++)
    {
        if(k==2)
        {
            if(r[(i+N-1)%N]!=r[i])
            {
                b=0;
                a++;
                con[i].push_back(make_pair(a,0));
                for(j=(i+1)%N;r[(j+N-1)%N]==r[i];j=(j+1)%N)
                {
                    if(j==N-1) ok=1;
                    if(r[i]==0) b--;
                    else b++;
                    con[j].push_back(make_pair(a,b));
                }
            }
        }
        else
        {
            for(i=0;i<N;i++)
            {
                if(r[i]==0)
                {
                    for(j=1;j<k;j++)
                    {
                        t=(i+j)%N;
                        Con[t]++;
                    }
                }
            }
            for(i=0;i<N;i++)
            {
                for(j=0;j<N;j++)
                {
                    if(use[j]==0&&Con[j]==0&&r[j]==0)
                    {
                        x=j;
                        break;
                    }
                }
                //printf("aa %d\n",x);
                what[x]=i;
                use[x]=1;
                for(j=1;j<k;j++)
                {
                    t=(x+j)%N;
                    Con[t]--;
                }
                for(j=1;j<k;j++)
                {
                    t=(x-j+2*N)%N;
                    r[t]--;
                    if(r[t]==0)
                    {
                        for(l=1;l<k;l++)
                        {
                            t2=(t+l)%N;
                            Con[t2]++;
                        }
                    }
                }
                //for(j=0;j<N;j++) if(!use[j]) printf("%d %d %d\n",j,r[j],Con[j]);

            }
        }
    }
	return;
}
bool F(int A,int B)
{
    if(A==B) return 1;
    if(use[A]) return 0;
    use[A]=1;
    for(auto i:Next[A]) if(F(i,B)) return 1;
    return 0;
}
int compare_plants(int x, int y)
{
    int i;
    if(tt)
    {
        for(auto i:con[x])
        {
            for(auto j:con[y])
            {
                if(i.first==j.first)
                {
                    if(i.second<j.second) return -1;
                    return 1;
                }
            }
        }

    }
    else
    {
        if(what[x]<what[y]) return 1;
        else return -1;
    }

	return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:17:21: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   17 |     int a=0,b=0,i,j,ok=0,l,t,t2,x;
      |                     ^~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:100:9: warning: unused variable 'i' [-Wunused-variable]
  100 |     int i;
      |         ^
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:17:33: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |     int a=0,b=0,i,j,ok=0,l,t,t2,x;
      |                                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 8 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 69 ms 12536 KB Output is correct
7 Correct 86 ms 13432 KB Output is correct
8 Correct 146 ms 20732 KB Output is correct
9 Correct 134 ms 20704 KB Output is correct
10 Correct 141 ms 20732 KB Output is correct
11 Correct 148 ms 20728 KB Output is correct
12 Correct 132 ms 20600 KB Output is correct
13 Correct 136 ms 20728 KB Output is correct
14 Correct 133 ms 20728 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 26 ms 9848 KB Output is correct
7 Correct 502 ms 12756 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 26 ms 9856 KB Output is correct
10 Correct 509 ms 12792 KB Output is correct
11 Correct 338 ms 12536 KB Output is correct
12 Correct 336 ms 12792 KB Output is correct
13 Correct 598 ms 12792 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 26 ms 9848 KB Output is correct
7 Correct 502 ms 12756 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 26 ms 9856 KB Output is correct
10 Correct 509 ms 12792 KB Output is correct
11 Correct 338 ms 12536 KB Output is correct
12 Correct 336 ms 12792 KB Output is correct
13 Correct 598 ms 12792 KB Output is correct
14 Execution timed out 4067 ms 12536 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 84 ms 12664 KB Output is correct
4 Execution timed out 4077 ms 15608 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Incorrect 7 ms 9728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Incorrect 7 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 8 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 69 ms 12536 KB Output is correct
7 Correct 86 ms 13432 KB Output is correct
8 Correct 146 ms 20732 KB Output is correct
9 Correct 134 ms 20704 KB Output is correct
10 Correct 141 ms 20732 KB Output is correct
11 Correct 148 ms 20728 KB Output is correct
12 Correct 132 ms 20600 KB Output is correct
13 Correct 136 ms 20728 KB Output is correct
14 Correct 133 ms 20728 KB Output is correct
15 Correct 7 ms 9728 KB Output is correct
16 Correct 7 ms 9728 KB Output is correct
17 Correct 7 ms 9728 KB Output is correct
18 Correct 7 ms 9728 KB Output is correct
19 Correct 7 ms 9728 KB Output is correct
20 Correct 26 ms 9848 KB Output is correct
21 Correct 502 ms 12756 KB Output is correct
22 Correct 9 ms 9728 KB Output is correct
23 Correct 26 ms 9856 KB Output is correct
24 Correct 509 ms 12792 KB Output is correct
25 Correct 338 ms 12536 KB Output is correct
26 Correct 336 ms 12792 KB Output is correct
27 Correct 598 ms 12792 KB Output is correct
28 Execution timed out 4067 ms 12536 KB Time limit exceeded
29 Halted 0 ms 0 KB -