oj.uz

Submission #426288

# Submission time Handle Problem Language Result Execution time Memory
426288 2021-06-13T16:59:30 Z duality The Collection Game (BOI21_swaps) C++14
15 / 100
 12 ms 352 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#include "swaps.h"

int used[500];
void solve(int N,int V) {
    int i,j;
    vi order;
    for (i = 0; i < N; i++) order.pb(i+1);
    int s = sqrt(N);
    for (j = N/4; j > 0; j -= s/2) {
        vi v1,v2;
        for (i = j; i < N; i++) {
            if (!used[i-j]) v1.pb(i),schedule(order[i-j],order[i]),used[i-j] = used[i] = 1;
            else v2.pb(i);
        }
        fill(used,used+N,0);
        vi r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v1[i]-j],order[v1[i]]);
        }
        for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
        r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v2[i]-j],order[v2[i]]);
        }
    }
    for (j = 0; j < 1.6*s; j++) {
        vi v1,v2;
        for (i = 1; i < N; i++) {
            if (i & 1) schedule(order[i-1],order[i]),v1.pb(i);
            else v2.pb(i);
        }
        vi r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v1[i]-1],order[v1[i]]);
        }
        for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
        r = visit();
        for (i = 0; i < r.size(); i++) {
            if (!r[i]) swap(order[v2[i]-1],order[v2[i]]);
        }
    }
    answer(order);
}

Compilation message

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-j],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 2 ms 200 KB Correct
3 Correct 4 ms 200 KB Correct
4 Correct 11 ms 312 KB Correct
5 Correct 12 ms 316 KB Correct
6 Correct 11 ms 316 KB Correct
7 Correct 11 ms 352 KB Correct
8 Correct 12 ms 316 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 1 ms 296 KB Correct
3 Correct 5 ms 200 KB Correct
4 Correct 11 ms 316 KB Correct
5 Correct 10 ms 312 KB Correct
6 Correct 11 ms 316 KB Correct
7 Correct 11 ms 304 KB Correct
8 Correct 11 ms 320 KB Correct
9 Correct 12 ms 316 KB Correct
10 Correct 11 ms 312 KB Correct
11 Correct 11 ms 312 KB Correct
12 Correct 12 ms 312 KB Correct
13 Correct 11 ms 316 KB Correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 300 KB Not correct

Subtask #4
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 300 KB Not correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Incorrect 2 ms 200 KB Not correct
3 Halted 0 ms 0 KB -