oj.uz

Submission #328060

# Submission time Handle Problem Language Result Execution time Memory
328060 2020-11-15T09:54:38 Z MonkeyKing JOIRIS (JOI16_joiris) C++14
100 / 100
 9 ms 768 KB 
//Original Code:
//#include <self/utility>
//#include <self/debug>
//using namespace std;
//int n,k;
//int a[55];
//int s[55];
//int g[55][2505];
//vector <pii> res;
//
//inline void error()
//{
//	cout<<-1<<endl;
//	exit(0);
//}
//
//inline void putV(int col)
//{
//	res.push_back(mp(1,col+1));
//	// cout<<1<<' '<<col+1<<endl;
//}
//
//inline void putH(int row)
//{
//	res.push_back(mp(2,row+1));
//	// cout<<2<<' '<<row+1<<endl;
//}
//
//int main()
//{
//	// freopen("input.txt","r",stdin);
//	// freopen("1.out","w",stdout);
//	// freopen("input.txt","r",stdin);
//	scanf("%d%d",&n,&k);
//	for(int i=0;i<n;i++)
//	{
//		scanf("%d",a+i);
//		s[i%k]+=a[i];
//	}
//	for(int i=0;i<k;i++)
//	{
//		s[i]%=k;
//	}
//	for(int i=0;i<n%k;i++)
//	{
//		if(s[i]!=s[0]) error();
//	}
//	for(int i=n%k+1;i<k;i++)
//	{
//		if(s[i]!=s[n%k]) error();
//	}
//	for(int i=1;i<n;i++)
//	{
//		while(a[i]<a[i-1])
//		{
//			a[i]+=k;
//			putV(i);
//		}
//	}
//	for(int i=0;i<n;i++)
//	{
//		for(int j=0;j<a[i];j++)
//		{
//			g[i][j]=true;
//		}
//	}
//	memset(s,0,sizeof(s));
//	for(int h=0;h<a[n-1];h++)
//	{
//		for(int i=n-1;i>=k-1;i--)
//		{
//			if(g[i][h]) continue;
//			putH(i-k+1);
//			for(int j=i-k+1;j<=i;j++)
//			{
//				s[j]++;
//				g[j][h]=true;
//			}
//		}
//	}
//	for(int i=0;i<k;i++)
//	{
//		for(int j=0;j<50;j++)
//		{
//			putV(i);
//		}
//		// cout<<a[i]<<' '<<s[i]<<' '<<k*k<<' '<<a[n-1]<<endl;
//		a[i]=a[i]+s[i]+50*k-a[n-1];
//	}
//	for(int i=0;i<k;i++)
//	{
//		// assert(a[i]<=k*k);
//		while(a[i]<50*k)
//		{
//			a[i]+=k;
//			putV(i);
//		}
//	}
//	for(int i=k;i<n;i++)
//	{
//		for(int j=0;j<50;j++)
//		{
//			putV(i);
//		}
//	}
//	for(int i=0;i<k;i++)
//	{
//		a[i]-=50*k;
//	}
//	if(n%k!=0)
//	{
//		int t=a[n%k-1];
//		while(t--)
//		{
//			for(int i=n%k;i<n;i+=k)
//			{
//				putH(i);
//			}
//		}
//	}
//	// for(int i=0;i<k;i++)
//	// {
//	// 	cout<<a[i]<<' ';
//	// }
//	// cout<<endl;
//	cout<<res.size()<<endl;
//	for(auto &p:res)
//	{
//		cout<<p.first<<' '<<p.second<<endl;
//	}
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <numeric>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#include <time.h>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define quickcin ios_base::sync_with_stdio(false);
#ifdef __TAKE_MOD
int mod;
#else
#ifdef __TAKE_CONST_MOD
const int mod=__TAKE_CONST_MOD;
#else
const int mod=1000000007;
#endif
#endif
const int gmod=5;
const int inf=1039074182;
const double eps=1e-9;
const ll llinf=2LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
template <typename T> inline T mabs(T x) {return (x<0?-x:x);}
#endif
using namespace std;
#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, vector<T> vec)
{
	cout << "{";
	for (int i = 0; i < (int)vec.size(); i++)
	{
		cout << vec[i];
		if (i != (int)vec.size() - 1)
			cout << ',';
	}
	cout << "}";
	return cout;
}

template <typename T>
void operator*=(vector<T> &vec, int k)
{
	for (auto &x : vec)
		x *= k;
}

template <typename T>
void operator-=(vector<T> &a, const vector<T> &b)
{
	assert(a.size() == b.size());
	for (size_t it = 0; it < a.size(); it++)
	{
		a[it] -= b[it];
	}
}

template <typename T>
vector<T> operator*(const vector<T> &vec, int k)
{
	vector<T> res(vec);
	res *= k;
	return res;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p)
{
	cout << "(" << p.first << ',' << p.second << ")";
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T>
ostream &operator<<(ostream &cout, queue<T> q)
{
	vector<T> t;
	while (q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout << t;
	return cout;
}

template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m)
{
	for (auto &x : m)
	{
		cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
	}
	return cout;
}

template <typename T>
T operator*(vector<T> v1, vector<T> v2)
{
	assert(v1.size() == v2.size());
	int n = v1.size();
	T res = 0;
	for (int i = 0; i < n; i++)
	{
		res += v1[i] * v2[i];
	}
	return res;
}

template <typename T1, typename T2>
pair<T1, T2> operator+(pair<T1, T2> x, pair<T1, T2> y)
{
	return make_pair(x.first + y.first, x.second + y.second);
}

template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, pair<T1, T2> y)
{
	x.first += y.first;
	x.second += y.second;
}

template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x)
{
	return make_pair(-x.first, -x.second);
}

template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec)
{
	vector<vector<T>> v;
	int n = vec.size(), m = vec[0].size();
	v.resize(m);
	for (int i = 0; i < m; i++)
	{
		v[i].resize(n);
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			v[i][j] = vec[j][i];
		}
	}
	return v;
}
#endif
void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<(int)vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	reverse(vec.begin(),vec.end());
	for(int i=(int)vec.size();i<len;i++)
	{
		putchar('0');
	}
	for(size_t i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}
#endif
using namespace std;
int n,k;
int a[55];
int s[55];
int g[55][2505];
vector <pii> res;

inline void error()
{
	cout<<-1<<endl;
	exit(0);
}

inline void putV(int col)
{
	res.push_back(mp(1,col+1));
	// cout<<1<<' '<<col+1<<endl;
}

inline void putH(int row)
{
	res.push_back(mp(2,row+1));
	// cout<<2<<' '<<row+1<<endl;
}

int main()
{
//	// freopen("input.txt","r",stdin);
	// freopen("1.out","w",stdout);
//	// freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
		s[i%k]+=a[i];
	}
	for(int i=0;i<k;i++)
	{
		s[i]%=k;
	}
	for(int i=0;i<n%k;i++)
	{
		if(s[i]!=s[0]) error();
	}
	for(int i=n%k+1;i<k;i++)
	{
		if(s[i]!=s[n%k]) error();
	}
	for(int i=1;i<n;i++)
	{
		while(a[i]<a[i-1])
		{
			a[i]+=k;
			putV(i);
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<a[i];j++)
		{
			g[i][j]=true;
		}
	}
	memset(s,0,sizeof(s));
	for(int h=0;h<a[n-1];h++)
	{
		for(int i=n-1;i>=k-1;i--)
		{
			if(g[i][h]) continue;
			putH(i-k+1);
			for(int j=i-k+1;j<=i;j++)
			{
				s[j]++;
				g[j][h]=true;
			}
		}
	}
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<50;j++)
		{
			putV(i);
		}
		// cout<<a[i]<<' '<<s[i]<<' '<<k*k<<' '<<a[n-1]<<endl;
		a[i]=a[i]+s[i]+50*k-a[n-1];
	}
	for(int i=0;i<k;i++)
	{
		// assert(a[i]<=k*k);
		while(a[i]<50*k)
		{
			a[i]+=k;
			putV(i);
		}
	}
	for(int i=k;i<n;i++)
	{
		for(int j=0;j<50;j++)
		{
			putV(i);
		}
	}
	for(int i=0;i<k;i++)
	{
		a[i]-=50*k;
	}
	if(n%k!=0)
	{
		int t=a[n%k-1];
		while(t--)
		{
			for(int i=n%k;i<n;i+=k)
			{
				putH(i);
			}
		}
	}
	// for(int i=0;i<k;i++)
	// {
	// 	cout<<a[i]<<' ';
	// }
	// cout<<endl;
	cout<<res.size()<<endl;
	for(auto &p:res)
	{
		cout<<p.first<<' '<<p.second<<endl;
	}
	return 0;
}

Compilation message

joiris.cpp: In function 'int main()':
joiris.cpp:396:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  396 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
joiris.cpp:399:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  399 |   scanf("%d",a+i);
      |   ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 8 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 9 ms 620 KB Output is correct
6 Correct 9 ms 748 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 6 ms 620 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 4 ms 492 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 9 ms 748 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 4 ms 492 KB Output is correct
23 Correct 7 ms 620 KB Output is correct
24 Correct 7 ms 620 KB Output is correct
25 Correct 8 ms 620 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 9 ms 640 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 8 ms 620 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 0 ms 364 KB Output is correct
33 Correct 0 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 0 ms 364 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 7 ms 620 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 8 ms 620 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 3 ms 492 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 9 ms 620 KB Output is correct
22 Correct 9 ms 748 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 6 ms 620 KB Output is correct
25 Correct 5 ms 492 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 5 ms 492 KB Output is correct
28 Correct 5 ms 492 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 3 ms 492 KB Output is correct
32 Correct 4 ms 492 KB Output is correct
33 Correct 0 ms 364 KB Output is correct
34 Correct 0 ms 364 KB Output is correct
35 Correct 9 ms 748 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 2 ms 364 KB Output is correct
38 Correct 4 ms 492 KB Output is correct
39 Correct 7 ms 620 KB Output is correct
40 Correct 7 ms 620 KB Output is correct
41 Correct 8 ms 620 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Correct 9 ms 640 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 8 ms 620 KB Output is correct
46 Correct 1 ms 364 KB Output is correct
47 Correct 1 ms 364 KB Output is correct
48 Correct 0 ms 364 KB Output is correct
49 Correct 0 ms 364 KB Output is correct
50 Correct 1 ms 364 KB Output is correct
51 Correct 1 ms 364 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 1 ms 364 KB Output is correct
54 Correct 0 ms 364 KB Output is correct
55 Correct 0 ms 364 KB Output is correct
56 Correct 1 ms 364 KB Output is correct
57 Correct 1 ms 364 KB Output is correct
58 Correct 1 ms 364 KB Output is correct
59 Correct 1 ms 364 KB Output is correct
60 Correct 2 ms 364 KB Output is correct
61 Correct 3 ms 364 KB Output is correct
62 Correct 3 ms 364 KB Output is correct
63 Correct 3 ms 492 KB Output is correct
64 Correct 4 ms 492 KB Output is correct
65 Correct 4 ms 492 KB Output is correct
66 Correct 2 ms 364 KB Output is correct
67 Correct 4 ms 492 KB Output is correct
68 Correct 5 ms 492 KB Output is correct
69 Correct 6 ms 492 KB Output is correct
70 Correct 8 ms 620 KB Output is correct
71 Correct 8 ms 620 KB Output is correct
72 Correct 8 ms 620 KB Output is correct
73 Correct 9 ms 620 KB Output is correct
74 Correct 9 ms 620 KB Output is correct
75 Correct 8 ms 620 KB Output is correct
76 Correct 9 ms 768 KB Output is correct
77 Correct 0 ms 364 KB Output is correct
78 Correct 7 ms 620 KB Output is correct
79 Correct 1 ms 364 KB Output is correct
80 Correct 1 ms 364 KB Output is correct
81 Correct 9 ms 748 KB Output is correct
82 Correct 7 ms 620 KB Output is correct
83 Correct 1 ms 364 KB Output is correct
84 Correct 1 ms 364 KB Output is correct
85 Correct 1 ms 364 KB Output is correct
86 Correct 2 ms 364 KB Output is correct
87 Correct 0 ms 364 KB Output is correct
88 Correct 0 ms 364 KB Output is correct
89 Correct 1 ms 364 KB Output is correct
90 Correct 1 ms 364 KB Output is correct
91 Correct 0 ms 364 KB Output is correct
92 Correct 8 ms 620 KB Output is correct