oj.uz

Submission #426289

# Submission time Handle Problem Language Result Execution time Memory
426289 2021-06-13T17:00:18 Z duality The Collection Game (BOI21_swaps) C++14
20 / 100
 16 ms 408 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),c = 0;
    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]]);
        }
        c += 2;
    }
    for (j = 0; j < (100-c)/2; 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:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
swaps.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (i = 0; i < v2.size(); i++) schedule(order[v2[i]-1],order[v2[i]]);
      |                     ~~^~~~~~~~~~~
swaps.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 3 ms 200 KB Correct
3 Correct 7 ms 200 KB Correct
4 Correct 12 ms 408 KB Correct
5 Correct 16 ms 316 KB Correct
6 Correct 15 ms 316 KB Correct
7 Correct 12 ms 312 KB Correct
8 Correct 13 ms 308 KB Correct

Subtask #2
10.0 / 10.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 3 ms 200 KB Correct
4 Correct 5 ms 200 KB Correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 300 KB Correct
4 Incorrect 10 ms 308 KB Not correct

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 4 ms 200 KB Correct
3 Correct 7 ms 300 KB Correct
4 Incorrect 10 ms 308 KB Not correct

Subtask #7
0 / 9.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 21.0

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

Subtask #10
0 / 14.0

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

Subtask #11
0 / 9.0

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

Subtask #12
0 / 6.0

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