oj.uz

Submission #427279

# Submission time Handle Problem Language Result Execution time Memory
427279 2021-06-14T13:54:53 Z model_code Power plants (CPSPC17_power) C++17
35 / 100
 5000 ms 1388 KB 
// Slow solution, but fits in memory, 35/100
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

typedef long long LL;

const int maxn = 200200;

struct point
{
    int x, y;
};

LL dist(point p1, point p2)
{
    LL x = p1.x - p2.x;
    LL y = p1.y - p2.y;
    return x*x + y*y;
}

point P[maxn];

vector<int> col;


bool dfs(int x, int n, LL s)
{
    bool ok = true;
    for(int y=0; y<n; y++)
    {
        if ((x==y) || (dist(P[x],P[y])>=s))
            continue;
        if (col[y]==col[x])
            return false;
        if (col[y]==-1)
        {
            col[y] = !col[x];
            ok &= dfs(y,n,s);
            if (!ok)
                return false;
        }
    }
    return ok;
}

bool check(int n, LL s)
{
    col.clear();
    col.resize(n,-1);
    bool ok = true;
    for(int i=0; i<n; i++)
        if (col[i]==-1)
        {
            col[i] = 0;
            ok &= dfs(i,n,s);
        }
    return ok;
}



int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d %d",&P[i].x, &P[i].y);
    LL p = 1;
    LL q = 2e18+1;
    while(p<q)
    {
        int s = (p+q+1)/2;
        if (check(n,s))
            p = s;
        else
            q = s-1;
    }
    assert(check(n,p));    
    vector<int> R[2];
    for(int i=0; i<n; i++)
        R[col[i]].push_back(i);
    
    printf("%Ld\n",p);
    for(int h=0; h<2; h++)
    {
        printf("%d\n",(int)R[h].size());
        for(int i=0; i<(int)R[h].size(); i++)
            printf((i ? " %d" : "%d"),R[h][i]+1);
        printf("\n");
    }
    
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d",&P[i].x, &P[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 200 ms 284 KB Output is correct
11 Correct 171 ms 280 KB Output is correct
12 Correct 158 ms 296 KB Output is correct
13 Correct 178 ms 300 KB Output is correct
14 Correct 149 ms 452 KB Output is correct
15 Correct 145 ms 356 KB Output is correct
16 Correct 199 ms 284 KB Output is correct
17 Correct 200 ms 324 KB Output is correct
18 Correct 178 ms 428 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 200 ms 284 KB Output is correct
11 Correct 171 ms 280 KB Output is correct
12 Correct 158 ms 296 KB Output is correct
13 Correct 178 ms 300 KB Output is correct
14 Correct 149 ms 452 KB Output is correct
15 Correct 145 ms 356 KB Output is correct
16 Correct 199 ms 284 KB Output is correct
17 Correct 200 ms 324 KB Output is correct
18 Correct 178 ms 428 KB Output is correct
19 Execution timed out 5052 ms 1388 KB Time limit exceeded
20 Halted 0 ms 0 KB -