oj.uz

Submission #127790

# Submission time Handle Problem Language Result Execution time Memory
127790 2019-07-10T06:10:36 Z dolphingarlic Gondola (IOI14_gondola) C++14
55 / 100
 23 ms 2404 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int valid(int n, int inputSeq[]) {
    bool in[250001];
    FOR(i, 0, n) {
        if (in[inputSeq[i]]) return 0;
        in[inputSeq[i]] = true;
    }

    FOR(i, 0, n) {
        if (inputSeq[i] <= n) {
            FOR(j, 1, n + 1) {
                int k = (i + j - inputSeq[i]) % n;
                while (k < 0) k += n;
                if (inputSeq[k] <= n && inputSeq[k] != j) return 0;
            }
            return 1;
        }
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	vector<pair<int, int>> broken;
	int offset = 0;
	FOR(i, 0, n) {
		if (gondolaSeq[i] > n) broken.push_back({gondolaSeq[i], i + 1});
		else offset = i - gondolaSeq[i] + 1;
	}
	FOR(i, 0, broken.size()) {
		broken[i].second = (broken[i].second - offset - 1 + n) % n + 1;
	}

	int indx = 0, curr = n;
	sort(broken.begin(), broken.end());
	for (pair<int, int> i : broken) {
		replacementSeq[indx++] = i.second;
		curr++;
		FOR(j, curr, i.first) replacementSeq[indx++] = j;
		curr = i.first;
	}

    return indx;
}

//----------------------

int countReplacement(int n, int inputSeq[]) {
    return -3;
}

Compilation message

gondola.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")
 
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:4:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
gondola.cpp:38:6:
  FOR(i, 0, broken.size()) {
      ~~~~~~~~~~~~~~~~~~~                
gondola.cpp:38:2: note: in expansion of macro 'FOR'
  FOR(i, 0, broken.size()) {
  ^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:12:27: warning: 'in[<unknown>]' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (in[inputSeq[i]]) return 0;
             ~~~~~~~~~~~~~~^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 13 ms 888 KB Output is correct
8 Correct 11 ms 760 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 13 ms 888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 352 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 14 ms 868 KB Output is correct
8 Correct 11 ms 764 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 13 ms 760 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 8 ms 760 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 15 ms 892 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 13 ms 760 KB Output is correct
12 Correct 13 ms 760 KB Output is correct
13 Correct 18 ms 1404 KB Output is correct
14 Correct 11 ms 760 KB Output is correct
15 Correct 23 ms 2404 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -