// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;// 1000000007
const ld pi = 3.1415926535;
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test1")
freopen((s + ".out").c_str(), "w", stdout);
}
}
#ifndef arwaeystoamneg
#include "doll.h"
#endif
#ifdef arwaeystoamneg
namespace {
constexpr int P_MAX = 20000000;
constexpr int S_MAX = 400000;
int M, N;
std::vector<int> A;
bool answered;
int S;
std::vector<int> IC, IX, IY;
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
void wrong_answer(const char* MSG) {
printf("Wrong Answer: %s\n", MSG);
exit(0);
}
void simulate() {
if (S > S_MAX) {
char str[50];
sprintf(str, "over %d switches", S_MAX);
wrong_answer(str);
}
for (int i = 0; i <= M; ++i) {
if (!(-S <= IC[i] && IC[i] <= M)) {
wrong_answer("wrong serial number");
}
}
for (int j = 1; j <= S; ++j) {
if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
wrong_answer("wrong serial number");
}
if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
wrong_answer("wrong serial number");
}
}
int P = 0;
std::vector<bool> state(S + 1, false);
int pos = IC[0];
int k = 0;
FILE* file_log = fopen("log.txt", "w");
fprintf(file_log, "0\n");
for (;;) {
fprintf(file_log, "%d\n", pos);
if (pos < 0) {
if (++P > P_MAX) {
fclose(file_log);
char str[50];
sprintf(str, "over %d inversions", P_MAX);
wrong_answer(str);
}
state[-pos] = !state[-pos];
pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
}
else {
if (pos == 0) {
break;
}
if (k >= N) {
fclose(file_log);
wrong_answer("wrong motion");
}
if (pos != A[k++]) {
fclose(file_log);
wrong_answer("wrong motion");
}
pos = IC[pos];
}
}
fclose(file_log);
if (k != N) {
wrong_answer("wrong motion");
}
for (int j = 1; j <= S; ++j) {
if (state[j]) {
wrong_answer("state 'Y'");
}
}
printf("Accepted: %d %d\n", S, P);
}
} // namespace
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
if (answered) {
wrong_answer("answered not exactly once");
}
answered = true;
// check if input format is correct
if ((int)C.size() != M + 1) {
wrong_answer("wrong array length");
}
if (X.size() != Y.size()) {
wrong_answer("wrong array length");
}
S = X.size();
IC = C;
IX = X;
IY = Y;
}
#endif
int n, m;
vi a, ans;
const int MAX = 4e5;
int x[MAX], y[MAX];
int cur = 1;
void solve(int i, vi& a)
{
if (sz(a) == 0)return;
if (sz(a) == 1)
{
x[i] = i;
y[i] = -a[0] - 1;
return;
}
vi t1, t2;
F0R(i, sz(a))if (i & 1)t2.pb(a[i]); else t1.pb(a[i]);
if (sz(a) % 2 == 0)
{
x[i] = cur;
solve(cur++, t1);
y[i] = cur;
solve(cur++, t2);
return;
}
x[i] = cur;
y[cur] = i;
x[cur] = cur + 1;
cur++;
solve(cur, t2);
y[i] = cur;
solve(cur++, t1);
}
void create_circuit(int M, std::vector<int> A) {
m = M;
n = sz(A);
a = A;
ans.rsz(m + 1);
ans[0] = a[0];
vector<vi>adj(m);
F0R(i, n - 1)
{
adj[a[i] - 1].pb(a[i + 1] - 1);
}
adj[a[n - 1] - 1].pb(-1);
F0R(i, m)
{
if (sz(adj[i]) == 0)continue;
if (sz(adj[i]) == 1)
{
ans[i + 1] = adj[i][0] + 1;
continue;
}
ans[i + 1] = -cur;
solve(cur++, adj[i]);
}
vi t1, t2;
FOR(i, 1, cur)t1.pb(-x[i]), t2.pb(-y[i]);
answer(ans, t1, t2);
}
#ifdef arwaeystoamneg
int main() {
setIO("test1");
M = read_int();
N = read_int();
A.resize(N);
for (int k = 0; k < N; ++k) {
A[k] = read_int();
}
answered = false;
create_circuit(M, A);
if (!answered) {
wrong_answer("answered not exactly once");
}
for (int i = 0; i <= M; ++i) {
cout << IC[i] << " ";
}
cout << endl;
for (int j = 1; j <= S; ++j) {
cout << IX[j - 1] << " " << IY[j - 1] << endl;
}
cout << endl;
simulate();
return 0;
}
#endif
Compilation message
doll.cpp: In function 'void setIO(std::string)':
doll.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:51:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6604 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
13 ms |
3820 KB |
Output is correct |
| 6 |
Correct |
41 ms |
8092 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6604 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
13 ms |
3820 KB |
Output is correct |
| 6 |
Correct |
41 ms |
8092 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Incorrect |
95 ms |
12336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
37 ms |
6604 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5440 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
13 ms |
3820 KB |
Output is correct |
| 6 |
Correct |
41 ms |
8092 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Incorrect |
95 ms |
12336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
wrong motion |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
wrong motion |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
wrong motion |
| 2 |
Halted |
0 ms |
0 KB |
- |
