Submission #127790

#	Time	Username	Problem	Language	Result	Execution time	Memory
127790		dolphingarlic	Gondola (IOI14_gondola)	C++14	55 / 100	23 ms	2404 KiB

gondola

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10