Submission #1697705


Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 2005;

class Edge {
public:
  int nxt, to;
} e[MAX_N * MAX_N];

int head[MAX_N], cnt;

void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N, A[MAX_N], top, res[MAX_N], len, st[MAX_N];
vector<int> G[MAX_N];
bool vis[MAX_N];

void dfs(int u, int v) {
  vis[u] = 1, st[++top] = u;
  sort(G[u].begin(), G[u].end());

  for (int i = 0; i < G[u].size(); ++i)
    if (!vis[G[u][i]]) {
      dfs(G[u][i], u);
    }
}

void merge_array() {
  static int temp[MAX_N];
  for (int i = 1; i <= len; ++i) temp[i] = res[i];
  int l1 = 1, l2 = 1, tlen = 0;
  while (l1 <= top || l2 <= len) {
    if (l1 > top) res[++tlen] = temp[l2++];
    else if (l2 > len) res[++tlen] = st[l1++];
    else if (st[l1] > temp[l2]) res[++tlen] = st[l1++];
    else res[++tlen] = temp[l2++];
  }
  len = tlen;
}

int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
  sort(A + 1, A + N + 1);
  
  for (int i = 1; i <= N; ++i)
    for (int j = i + 1; j <= N; ++j)
      if (__gcd(A[i], A[j]) != 1) {
	G[i].push_back(j);
	G[j].push_back(i);
      }
  
  for (int i = 1; i <= N; ++i) 
    if (!vis[i]) {
      top = 0, dfs(i, 0);
      merge_array();
    }

  for (int i = 1; i <= N; ++i)
    printf("%d ", A[res[i]]);
  puts("");
  
  return 0;
}

Submission Info

Submission Time
Task E - Rearranging
User kiiiiii
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1508 Byte
Status WA
Exec Time 280 ms
Memory 17664 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:50:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
                                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1600
Status
AC × 2
AC × 15
WA × 34
Set Name Test Cases
Sample sample1.txt, sample2.txt
All sample1.txt, sample2.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in4.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
in1.txt WA 278 ms 10112 KB
in10.txt WA 280 ms 10624 KB
in11.txt WA 222 ms 1536 KB
in12.txt WA 223 ms 1536 KB
in13.txt WA 221 ms 1536 KB
in14.txt WA 223 ms 1536 KB
in15.txt WA 223 ms 1536 KB
in16.txt WA 259 ms 17664 KB
in17.txt AC 259 ms 17664 KB
in18.txt WA 258 ms 17664 KB
in19.txt AC 259 ms 17664 KB
in2.txt WA 278 ms 10112 KB
in20.txt WA 259 ms 17664 KB
in21.txt AC 171 ms 384 KB
in22.txt AC 171 ms 384 KB
in23.txt WA 172 ms 384 KB
in24.txt AC 171 ms 384 KB
in25.txt AC 171 ms 384 KB
in26.txt WA 222 ms 1536 KB
in27.txt WA 223 ms 1536 KB
in28.txt WA 221 ms 1536 KB
in29.txt WA 223 ms 1536 KB
in3.txt WA 278 ms 9984 KB
in30.txt WA 222 ms 1536 KB
in31.txt AC 1 ms 256 KB
in32.txt AC 1 ms 256 KB
in33.txt AC 1 ms 256 KB
in34.txt AC 199 ms 384 KB
in35.txt AC 199 ms 384 KB
in36.txt WA 237 ms 3200 KB
in37.txt WA 236 ms 3200 KB
in38.txt WA 237 ms 3200 KB
in39.txt WA 238 ms 3200 KB
in4.txt WA 278 ms 9984 KB
in40.txt WA 236 ms 3072 KB
in41.txt WA 237 ms 3072 KB
in42.txt WA 237 ms 3072 KB
in43.txt WA 237 ms 3200 KB
in44.txt WA 237 ms 3072 KB
in45.txt WA 238 ms 3072 KB
in5.txt WA 278 ms 9728 KB
in6.txt WA 279 ms 10496 KB
in7.txt WA 279 ms 10624 KB
in8.txt WA 279 ms 10240 KB
in9.txt WA 278 ms 9984 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB